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:
For Example
Input Format :
Output Format :
Note :
Constraints:
Sample Input 1 :
Sample Output 1 :
Explanation For Sample Output 1:
Sample Input 2 :
Sample Output 2 :
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];elsedp[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.
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.