Problem:
Given a set of coins and an amount , find the minimum set of coins required to compute that amount.
For example ,
If you are given the set of coins 1,2 and 5 ,you need to compute the number of coins required to calculate the amount of 11 rupees.
Input:
Coins = [1,2,5]
Amount = 11
Assumptions:
- You have infinite supply of each type of coin
Output:
3 since the amount 11 can be calculated using two 5 rupee coins and one 1 rupee coin (5 + 5 + 1)
Try out the solution here:
https://leetcode.com/problems/coin-change
Solution:
Hint:
For every coin that you consider , find the minimum number of coins required for the difference between the current coin value and the amount.
Consider the input:
coins = [1,2,5]
amount = 4
You can calculate 4 using the above coins in several ways:
4 one rupee coins
2 two rupee coins
1 two rupee coin and 2 one rupee coins = total 3 coins
and so on.
The least combination is 2 two rupee coins.
How to calculate this?
Recursive solution:
Consider the coins [1,2,5] for the input 4.
Let’s assume you take 1 rupee coin first.
This means you have (4-1)= 3 rupees left now.
For this 3 rupees you can again choose from [1,2,5] coin set.
Lets choose 1 rupee again.
You have (3-1) = 2rupees left now.
For this 2 rupees you can again choose from [1,2,5] coins set.
Let’s choose 1 rupee again.
You have (2-1) = 1 rupees left now.
For this 1 rupee you can only choose 1 rupee from the coin set [1,2,5].
The remaining amount is 0 , so we have got a combination!
1 + 1 + 1 + 1
The number of coins required here is 4.
We only chose 1 rupee coins for each remaining amount.
What if we chose 2 rupees when the remaining amount was 2.
Then we would have got the combination 1 + 1 + 2
The number of coins required here is only 3.
Here is the recursive tree for the different combinations:
The combination we discussed is the left most one .
The one highlighted in red gives the combination with the minimum number of coins ( 2 rupee coin + 2 rupee coin = 2 coins)
In short , for every coin we find the minimum number of coins required for the remaining amount and add one to it (to include current coin)
For every amount we can choose either of the 3 coins (if the coin value is less than the amount) which gives different combinations as shown above.
Here is the recursive code for the same:
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0){
return 0;
}
int minCoin = Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++){
if(coins[i] <= amount){
int currentMin = coinChange(coins,amount-coins[i]);
int currentCount = currentMin + 1;
if(currentMin != -1 && currentCount < minCoin){
minCoin = currentCount;
}
}
}
if(minCoin == Integer.MAX_VALUE){
return -1;
}else{
return minCoin;
}
}
}
But it has a higher time complexity (exponential) . For each coin you make a recursive call which in turn makes m recursive calls (m is the total number of coins). You do this until the amount is 0. The time complexity is O(m^n) where n is the total amount.
You can improve the time complexity by storing the solutions of the recursive calls and returning it rather than computing them every time .
Here is the code:
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,-1);
return find(coins,amount,dp);
}
public int find(int[] coins,int amount,int[] dp){
if(amount ==0)return 0;
if(dp[amount] != -1) return dp[amount];
int minimum = Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++){
if(coins[i] <= amount){
int currentVal = find(coins,amount - coins[i],dp);
if(currentVal != -1 && currentVal + 1 < minimum){
minimum = currentVal+1;
}
}
}
if(minimum == Integer.MAX_VALUE){
return -1;
}
dp[amount] = minimum;
return minimum;
}
}
Still the time taken is quite high for higher inputs.
Dynamic Programming Bottom Up Approach:
In Dynamic Programming Bottom up approach,
You need to calculate the minimum number of coins required starting from 1 rupee to the given amount of rupees.
You need to use each coin for each rupee.
As you go through the above steps you need to find the minimum coins required before using the current coin and after using the current coin and choose the minimum of the two.
Minimum coins = Minimum of ( Minimum coins required before adding the current coin , Minimum coins required after adding the current coin)
Minimum coins required before adding the current coin would be already available as you reach the position of the coin in the current iteration.
To calculate the minimum coins required after adding the current coin, find the minimum coins required for (amount – current coin value) rupees and add 1 to it.
Note: You can consider a coin only if it is less than or equal to the given amount
Minimum coins after adding current coin = Minimum coins required for ( n – coins[i]) + 1
where n is the given input amount
coins[i] represent the current coin value.
So if 6 is the input amount and current coin value is 2 ,
You find the minimum coins required for (6-2) rupees which is 4 rupees. So If you add the current coin (2 rupees) to the above 4 rupees it gives the final amount . So the total number of coins is one more than the minimum coins required for (n – coins[i]) rupees.
Let us go back to the input:
[1,2,5]
Let us consider the amount : 6
Take a table.
Write the amount values in a row header
Write the coin values in the column header:
Here is the algorithm using Dynamic Programming:
The row values represent the minimum number of coins required for each amount given in the row header.
For each row , fill the minimum number of coins required for each amount.
Initially for the first row , we have the coin value as 1 (column header).
For 0 rupees you need 0 one rupee coin
For 1 rupee you need one rupee coin
For 2 rupees you need 2 one rupees coin and so on:
(You can use the formula given in the hint instead to get the same output)
Now let’s move to the next row .
As you move on to the next row you consider both the previous row coin and the current row coin.
We are using 2 rupee coin now.
So we need to consider the minimum number of 1 rupee and 2 rupee coins combined now.
For 0 rupees , the coin value is always 0.
For 1 rupee , the coin value 2 is greater , you cannot make 1rupees using 2 rupee coins. So ignore it and let the value from the previous row remain as such.
For 2 rupees:
Subtract the amount value from the coin value (2-2 = 0) , the value in 0th column for the second row is 0. You add 1 to it which gives 0+1 = 1.
Compare this value from the value already present for number of coins required for 2 rupees (from the previous row) which is 2 rupees ( 2 one rupee coins).
1 is less than 2 , so choose the value 1 and enter it in the second column of the second row.
Keep doing it until you reach the end of the row:
Do the same for the third row:
The final value in the last row , last column gives the required output (Number 2)
You need two coins (5 + 1) minimum to represent the amount 6.
ALGORITHM:
STEP1: If the amount is 0 , return 0
STEP2: Create an output change array to store the minimum number of coins required for each amount upto the given amount
STEP3: Initialize the first value to 0 , as for 0 rupees you need 0 coins.
STEP4: Initialize the other change values to the maximum possible value.
STEP5: For each amount value , check if coin value is less than or equal to the amount
STEP5a: If so , find the minimum number of coins required for the amount (amount – current coin value)
STEP5b: If the above computed value is less than the already computed minimum number of coins for the current amount , assign it as the minimum change required for that amount.
STEP6: If the final value in the output array is not the maximum value stored initially , return it. else return -1.
Code:
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0){
return 0;
}
//array to hold minimum coins for each amount until the given amount
int[] change = new int[amount+1];
//for 0 rupees you need 0 coins.
change[0] = 0;
//initialize all the minimum coin values to the maximum.
for(int i=1;i<=amount;i++){
change[i]= Integer.MAX_VALUE;
}
//Compare the minimum no of coins required without adding the current coin value (amount minus current coin value) - this value plus the current coin will give the amount. Compare this value with the already calculated minimum without using the current coin . That gives the final minimum value.
for(int i=1;i<=amount;i++){
for(int j=0;j<coins.length;j++){
if(coins[j] <= i){
int currentMin = change[i-coins[j]];
if(currentMin != Integer.MAX_VALUE && currentMin + 1 < change[i]){
change[i] = currentMin +1;
}
}
}
}
if(change[amount] == Integer.MAX_VALUE){
return -1;
}
return change[amount];
}
}
The time complexity of the above algorithm is (n * m ) where n represents the amount and m represents the number of coins.
The space complexity is O(n+1) which can be considered as O(n) (the output array used to store the values).
That’s it!
Leave a Reply