Skip to content

Add method for minimum number of coins required for given amount #468

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jul 30, 2018
Merged

Add method for minimum number of coins required for given amount #468

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
39 changes: 34 additions & 5 deletions Dynamic Programming/CoinChange.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,9 +10,11 @@ public class CoinChange {
public static void main(String[] args) {

int amount = 12;
int[] coins = {1, 2, 5};
int[] coins = {2, 4, 5};

System.out.println("Number of combinations of getting change for " + amount + " is: " + change(coins, amount));
System.out.println("Minimum number of coins required for amount :" + amount + " is: " + minimumCoins(coins, amount));

}

/**
Expand All @@ -29,22 +31,49 @@ public static int change(int[] coins, int amount) {

for (int coin : coins) {
for (int i=coin; i<amount+1; i++) {
combinations[i] += combinations[i-coin];
combinations[i] += combinations[i-coin];
}
// Uncomment the below line to see the state of combinations for each coin
// printAmount(combinations);
}

return combinations[amount];
}
/**
* This method finds the minimum number of coins needed for a given amount.
*
* @param coins The list of coins
* @param amount The amount for which we need to find the minimum number of coins.
* Finds the the minimum number of coins that make a given value.
**/
public static int minimumCoins(int[] coins, int amount) {
//minimumCoins[i] will store the minimum coins needed for amount i
int[] minimumCoins = new int[amount+1];

minimumCoins[0] = 0;

for(int i=1;i<=amount;i++){
minimumCoins[i]=Integer.MAX_VALUE;
}
for(int i=1;i<=amount;i++){
for (int coin :coins){
if(coin <=i){
int sub_res = minimumCoins[i-coin];
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < minimumCoins[i])
minimumCoins[i] = sub_res + 1;
}
}
}
// Uncomment the below line to see the state of combinations for each coin
//printAmount(minimumCoins);
return minimumCoins[amount];
}

// A basic print method which prints all the contents of the array
public static void printAmount(int[] arr) {

for (int i=0; i<arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

}
}