322 Coin Change/ Minimum Coins/Elements | Solution | 4 Approaches

Raunit Verma August 04, 2022

Coin Change/ Minimum Coins 


You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
CodeStudio

Problem Statement
Suggest Edit

You are given an array of ‘N’ distinct integers and an integer ‘X’ representing the target sum. You have to tell the minimum number of elements you have to take to reach the target sum ‘X’.

Note:
You have an infinite number of elements of each type.
For Example
If N=3 and X=7 and array elements are [1,2,3]. 
Way 1 - You can take 4 elements  [2, 2, 2, 1] as 2 + 2 + 2 + 1 = 7.
Way 2 - You can take 3 elements  [3, 3, 1] as 3 + 3 + 1 = 7.
Here, you can see in Way 2 we have used 3 coins to reach the target sum of 7.
Hence the output is 3.
Input Format :
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case will contain two space-separated integers ‘N’ and ‘X’, denoting the size of the array and the target sum.

The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.
Output Format :
For each test case, print the minimum number of coins needed to reach the target sum ‘X’, if it's not possible to reach to target then print "-1".

Print a separate line for each test case.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 15
1 <= nums[i] <= (2^31) - 1
1 <= X <= 10000

All the elements of the “nums” array will be unique.
Time limit: 1 sec
Sample Input 1 :
2
3 7
1 2 3
1 0
1
Sample Output 1 :
 3
 0
Explanation For Sample Output 1:
For the first test case,
Way 1 - You can take 4 elements  [2, 2, 2, 1] as 2 + 2 + 2 + 1 = 7.
Way 2 - You can take 3 elements  [3, 3, 1] as 3 + 3 + 1 = 7.
Here, you can see in Way 2 we have used 3 coins to reach the target sum of 7.
Hence the output is 3.

For the second test case,
Way 1 - You can take 3 elements  [1, 1, 1] as 1 + 1 + 1  = 3.
Way 2 - You can take 2 elements  [2, 1] as 2 + 1 = 3.
Here, you can see in Way 2 we have used 2 coins to reach the target sum of 7.
Hence the output is 2.
Sample Input 2 :
2
3 4
12 1 3
2 11
2 1
Sample Output 2 :
2
6





Solution:

The first thought would be greedy which uses the coins with max values and get the minimum number of coins.
 For Example - Let the array be [1,2,3] and the target be 7. Then we will take 7/3 = 2 coins of 3 and 1/1=1 coins of 1.
But where does it fails
Let us take the array as [9,6,5,1] and the target is 11.
so 11/9=1 coin of 9 and 2/1 =2 coins of 1 so a total of 3 coins. But we can have a better answer of 2 coins as 6 and 5 makes up a total of 11, so greedy here fails.

What we can do Now?
We can try out all combinations to form the target and then take the combo with minimum coins.

Rules:
1. Express everything in terms of index and target
2. Once the target is achieved take the minimum number of coins

f(ind,target){
int notTake=f(ind-1,target);
int take=INT_MAX;
if(arr[i]<=target)
take=1+f(ind,target-arr[ind])
return min(take,notTake);
}

Base Case:

1. if idx<0 return the max number of coins.

2. if target==0 return the number of coins. 


class Solution {
public:
    
    int helper(vector<int>&coins,int target,int idx){
        if(idx<0)return INT_MAX-5;
        if(target==0)return 0;
        int notTake=helper(coins,target,idx-1);
        int take=INT_MAX;
        if(coins[idx]<=target)take=1+helper(coins,target-coins[idx],idx);
        return min(take,notTake);
    }
    
    int coinChange(vector<int>& coins, int amount) {
        int k= helper(coins,amount,coins.size()-1);
        if(k==INT_MAX-5)return -1;
        return k;
    }
};


Time Complexity >>>> O(2^N)
Space Complexity >>>O(N) (auxiliary) with max of O(target) when coins if of only 1 value.

Memoization:

Make a vector of vectors and save the results of the functions called.

Code Here:


class Solution {
public:
    
    int helper(vector<int>&coins,int target,int idx,vector<vector<int>>&dp){
        if(idx<0)return INT_MAX-5;
        if(target==0)return dp[idx][target]=0;
        if(dp[idx][target]!=-1)return dp[idx][target];
        int notTake=helper(coins,target,idx-1,dp);
        int take=INT_MAX;
        if(coins[idx]<=target)take=1+helper(coins,target-coins[idx],idx,dp);
        return dp[idx][target]=min(take,notTake);
    }
    
    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>>dp(coins.size(),vector<int>(amount+1,-1));
        int k= helper(coins,amount,coins.size()-1,dp);
        if(dp[coins.size()-1][amount]==INT_MAX-5)return -1;
        return dp[coins.size()-1][amount];
    }
};



Time Complexity: O(target x N)
Space Complexity: O(N x target) + O(target)

Tabulation:

Base Case:
1. Declare the dp[N][target+1]
2. for(target: 0 ->target){

if(target%arr[0]==0)
    dp[0][target]=target/arr[0];
else 
    dp[0][target]=INT_MAX;

}
3.  idx : 1->n-1
    target: 0 -> target

class Solution {
public:
    
    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>>dp(coins.size(),vector<int>(amount+1,-1));
        for(int i=0; i<=amount; i++){
            if(i%coins[0]==0)dp[0][i]=i/coins[0];
            else dp[0][i]=INT_MAX-5;
        }
        for(int i=1; i<coins.size(); i++){
            for(int j=0; j<=amount; j++){
                int notTake=dp[i-1][j];
                int take=INT_MAX-5;
                    if(coins[i]<=j)take=1+dp[i][j-coins[i]];
                dp[i][j]=min(take,notTake);
            }
        }
        if(dp[coins.size()-1][amount]==INT_MAX-5)return -1;
        return dp[coins.size()-1][amount];
    }
};

Reducing Space from NxTarget+1 to two vectors of target+1.


class Solution {
public:
    
    int coinChange(vector<int>& coins, int amount) {
        vector<int>prev(amount+1,-1);
        for(int i=0; i<=amount; i++){
            if(i%coins[0]==0)prev[i]=i/coins[0];
            else prev[i]=INT_MAX-5;
        }
        for(int i=1; i<coins.size(); i++){
            vector<int>curr(amount+1,0);
            for(int j=0; j<=amount; j++){
                int notTake=prev[j];
                int take=INT_MAX-5;
                    if(coins[i]<=j)take=1+curr[j-coins[i]];
                curr[j]=min(take,notTake);
            }
            prev=curr;
        }
        if(prev[amount]==INT_MAX-5)return -1;
        return prev[amount];
    }
};


Thank You for reading.



Tags

Post a Comment

0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.