loading...

Daily Coding Challenge #29

wingkwong profile image wkw ・3 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

Input: amount = 10, coins = [10] 
Output: 1
*/

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // unbounded knapsack 
        vector<int> dp(amount+1,0);
        dp[0]=1;
        for(auto c:coins){
            for(int j=c;j<=amount;j++){
                dp[j]+=dp[j-c];
            }
        }
        return dp[amount];
    }
};
Enter fullscreen mode Exit fullscreen mode

/*
LeetCode - Power of Two

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1
Example 2:

Input: 16
Output: true
Explanation: 24 = 16
Example 3:

Input: 218
Output: false
*/

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // 8(n): 00001000
        // 7(n-1): 00000111
        // 8&7 (n&n-1) = 00000000 = 0
        return n>0&&!(n&(n-1));
    }
};
Enter fullscreen mode Exit fullscreen mode

/*
LeetCode - Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
*/

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int ssz=(int)s.size();
        int tsz=(int)t.size();
        int i=0,j=0;
        // two pointer approach
        for(;i<ssz&&j<tsz;j++){
            // if matched, move i to the next char in s
            if(s[i]==t[j]) i++;
        }
        // if i reaches the end, it means it is a subseqeunce
        return (i==ssz);
    }
};

class Solution2 {
public:
    bool isSubsequence(string s, string t) {
        // DP approach - similar to 1143. Longest Common Subsequence
        int m=(int)s.size(), n=(int)t.size();
        if(m==0) return true;
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==t[j-1]) {
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n]==m;
    }
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
Enter fullscreen mode Exit fullscreen mode

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / hackerrank

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / codeforces

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / atcoder

Migrated to https://github.com/wingkwong/competitive-programming

Discussion

pic
Editor guide