Leetcode- Sum of two integer

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Solution: bit-wise manipulation

Here are two integers a and b, if there is no carry occurring in the process then  a+b=a⊗b，Here ⊗ represents the XOR. The Carry bits appears when 1+1 so the carry bits of a+b can be represented as  2×(a & b)，& means AND operation, multiply 2 to shift left.

After N times of operation, the carry bit would be 0 then we can return the result;

The program can be easily written in recursive form

int getSum(int a, int b) { if(a == 0) return b; int x = a ^ b; int c = (a & b) << 1; return getSum(c, x); }

x0+c0

Read More

Leetcode--Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

---------------------------------------------------------------------------------------------

This is one of the easiest problem in leetcode.

To reverse the string, all we need to do is swap the first character with the last one and go on.

class Solution {
public:
    string reverseString(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            char t = s[left];
            s[left++] = s[right];
            s[right--] = t;
        }
        return s;
    }
};

Read More

Leetcode-Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution 1：Lagrange four square theorem

From Lagrange four square theorem, we can know that any natural number can represented 

by 4 square numbers. So the answer of this problem has been limited to 1~4.

The number can be written in form  

Then the Three square theorem then suggested that any number can satisfy the theorem above can 

also be represented by 3 square numbers.

So the situations can be handled respectively.

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;

        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }

        return 3;
    }
};

Solution 2 : Dynamic programming.

The problem is similar to the Coin change problem.

class Solution {
public:
    int numSquares(int n) {
       

        vector<int> dp(n+1,n+1);
        
        dp[0]=0;
        
        for(int i=1;i<=n;i++)
            for(int j=0;j*j<=n;j++){
                if(j*j<=i)
                    dp[i]=min(dp[i],dp[i-j*j]+1);
            }    
            
        return dp.back();

 

    }
};

Read More

Leecode Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

We can still apply the DFS method to count this, however, the cost will be too high that can't pass the time limit. This case is similar to the coin exchange problem. We can use dynamic programming concept to reuse the product during the process.

The code is also quite similar to coin exchange problem.

    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int x : nums) {
                if (i >= x) {
                    dp[i] += dp[i - x];
                }
            }
        }
        
        return dp[target];
    }

Noted that in Coin exchange problem 

dp[0] = 0. The definition was "the minimum coins used to combine the value", therefore

the minimum coins to combine "0" should be zero. And in coin exchange problem we initiate other elements in the vector to n+1 to make the min-comparison work.

Here,

the dp represents " all possible sets to combine the value" while we didn't initiate other elements in the vecotr. The empty set is also counted to combine the value 0 here. So dp[0] =1;

Read More

Leetcode- coin change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3

return -1.

Refer to : Coin change algorithm

Let's try to understand this algorithm using an example. If we are make change of 50 using infinite number of coins of denominations {20,10,5,1} then 

total number of ways to make change of 50 using denominations {20,10,5,1} = total number of ways to make change of 50 using 0 coins of 20 + total number of ways to make change of 50 using 1 coin of 20 + total number of ways to make change of 50 using 2 coins of 20

Now first term on the right hand side of above equation that is - total number of ways to make change of 50 using 0 coins of 20 can be restated as total number of ways to make change of 50 using denominations {10,5,1}

And second term that is total number of ways to make change of 50 using 1 coin of 20 = total number of ways to make change of 30 using denominations {10,5,1}
Similarly, total number of ways to make change of 50 using 2 coins of 20 = total number of ways to make change of 10 using denominations {10,5,1}.As you can see, this algorithm is recursive in nature and the recursion tree for the above example looks like following. Only one complete path is shown in recursion tree due to space constraint.

The base case for this algorithm would be when the denomination set has only coins of 1 in it. In that case total number of ways to make change would be 1. Also when amount to make change of is 0, total number of ways to make change would be 1(0 coins of all denominations).

The formal steps of this algorithm are - 
1. If the current denomination is 1 then return 1. This is the base case.

2. If current denomination is 20, set next denomination as 10; if current denomination is 10, set next denomination as 5 and if current denomination is 5, set next denomination as 1.
3. Now implement the recurrence relation: numberOfWays(amount, denom) =  numberOfWays(amount - 0*denom, nextDenom) + numberOfWays(amount - 1*denom, nextDenom) + ... + numberOfWays(0, nextDenom) using a while loop.

The time complexity of this algorithm is exponential as can be easily observed from recursion tree.

Dynamic Programming - Memoization approach: For the same example, if we look at the recursion tree shown below which highlights the re-computations for the sub-problems of n = 30 and  denominations = {5,1}, n = 20 and  denominations = {5,1} and so on.

To avoid these re-computations, we could store the results when computed and re-use them if required again. This reduces the time complexity of this algorithm to O(nm) where n is total amount to make change for and m is total number of denominations. For the example shown in the recursion tree n would be 50 and m would be 4. This approach takes extra space of O(nm).

Let dp[v] to be the minimum number of coins required to get the amount v. 
dp[i+a_coin] = min(dp[i+a_coin], dp[i]+1) if dp[i] is reachable. 
dp[i+a_coin] = dp[i+a_coin] is dp[i] is not reachable.  

We initially set dp[i] to be MAX_VALUE.  !!

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        // The combinations of each coin can't be larger than amount.
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        //minimun amount of coin to reach 0 value
        for (int i = 1; i < amount + 1; ++i)
            for (int j = 0; j < coins.size(); ++j)
                if (coins[j] <= i)
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);

        return dp[amount] > amount ? -1 : dp[amount];
      // amount+1 means the dp value was unchanged meaning that 
     //it can't be further combined by other coins

    }
};

Read More

Leetcode - Combination / Combination sum 1/2/3

1. Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

In this kind problem, we will need to go through from 1 to n in increasing order.

We need to apply the Backtracking method here to solve this problem. Backtraking

And the Depth First Search style algorithm can be applied to the scenario give all the possible

solutions to the problem.

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> ret;
        if(n <= 0) //corner case invalid check
            return ret;

        vector<int> curr;
        DFS(ret,curr, n, k, 1); //we pass ret as reference at here
        return ret;
    }

    void DFS(vector<vector<int>>& ret, vector<int> curr, int n, int k, int level)
    {
        if(curr.size() == k)
        {
            ret.push_back(curr);
            return;
        }
        if(curr.size() > k)  // consider this check to save run time
            return;

        for(int i = level; i <= n; ++i)
        {
            curr.push_back(i);
            DFS(ret,curr,n,k,i+1);
            curr.pop_back();
        }
    }

};

2. Combination sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

[
  [7],
  [2, 2, 3]
]

In this case, we apply DFS and backtracking to solve this problem. Noted that we will sort the

candidates first and during the loop we will skip to the last element of same values.

class Solution { public: vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > allSol; vector<int> sol; if(candidates.empty()) return allSol; sort(candidates.begin(),candidates.end()); findCombSum(candidates, 0, target, sol, allSol); return allSol; } void findCombSum(vector<int> &candidates, int start, int target, vector<int> &sol, vector<vector<int>> &allSol) { if(target==0) { allSol.push_back(sol); return; } for(int i=start; i<candidates.size(); i++) { if(i>start && candidates[i]==candidates[i-1]) continue; if(candidates[i]<=target) { sol.push_back(candidates[i]); findCombSum(candidates, i, target-candidates[i], sol, allSol); sol.pop_back(); } if(candidates[i]>target) return; //This can save the runtime } } };

3. Combination sum 2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Comparing to combination sum 1, the answer can't contain duplicate numbers.

All we need to do is increment the the i- value to accomplish this part.

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > allSol;
        if(num.empty()) return allSol;
        sort(num.begin(),num.end());
        vector<int> sol;
        findCombSum2(num, 0, target, sol, allSol);
        return allSol;
    }
    
    void findCombSum2(vector<int> &num, int start, int target, vector<int> &sol, vector<vector<int> > &allSol) {
        if(target==0) {
            allSol.push_back(sol);
            return;
        }
        
        for(int i=start; i<num.size(); i++) {
            if(i>start && num[i]==num[i-1]) continue;
            if(num[i]<=target) {
                sol.push_back(num[i]);
                findCombSum2(num, i+1, target-num[i], sol, allSol);
                sol.pop_back();
            }
        }
    }
};

4. Combination sum 3

.Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};

Read More

Iterative DFS and Recursive DFS

Iterative DFS

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

Recursive DFS

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

A DFS does not specify which node you see first. 
It is not important because the order between edges is not defined 

Read More