In this article we'll see how to write a Java program for the coin change problem, which states that "Given an array of coins storing coins of different denominations and an integer sum representing an amount. Find the minimum number of coins needed to make that sum. If that amount of money cannot be made up by any combination of the coins, return -1."
Any coin can be used any number of times.
For example-
1. Input: int coins[] = {9, 6, 5, 1}, sum = 101
Output: 12
How: 9 (10 times) + 6 + 5
2. Input: int coins[] = {1, 2, 5}, sum = 11
Output: 3
How: 5 + 5 + 1
3. Input: int coins[] = {2}, sum = 0
Output: 0
The "coin change" problem is a good example of dynamic programming as you can break this problem into smaller overlapping sub-problems and you can also store the result of those subproblems (memoization) to avoid redundant calculations.
Coin change problem Java Program
The program for finding the minimum number of coins that add to the given sum can be written using
- Recursion without any optimization.
- You can add memoization with recursion to make it faster this is also called top-down approach in dynamic programming.
- You can also use bottom-up approach also known as tabular form. In bottom-up approach you try to solve the sub-problems first and use their solutions to arrive at solutions to bigger sub-problems.
We'll write java programs for all these three approaches here.
1. Using recursion
Here the approach is, if for the selected coin, sum - coin >= 0, i.e. coin can be used to get the sum then we have to recursively call the method with the rest of the amount (sum-coin). You also need to ensure that you take the minimum of current count and the result of adding selected coin to count.count = Math.min(count, res+1);
Here is the complete Java program with the recursive method.
public class MinCoinSum {
public static void main(String[] args) {
int coins[] = {9, 6, 5, 1};
int sum = 10;
int c = minCoinsNeeded(coins, sum);
System.out.println("Coins needed- " c);
}
private static int minCoinsNeeded(int[] coins, int sum) {
if(sum == 0) {
return 0;
}
int count = Integer.MAX_VALUE;
int res = 0;
for(int coin : coins) {
if(sum - coin >= 0) {
res = minCoinsNeeded(coins, sum-coin);
if(res != -1) {
// if coin needed; that is include
// scenario (res+1) otherwise you go with count
count = Math.min(count, res+1);
}
}
}
return (count == Integer.MAX_VALUE) ? -1 : count;
}
}
Output
Coins needed- 2
Time and space complexity with this approach
With this approach each recursive call tries all coin denominations. If amount is n and the number of coins is c then the time complexity is O(cn)
Recursion stack depth will be n so, the space complexity is O(n).
2. Using memoization with recursion
With the above recursive method there are many repetitive calls. Memoization improves this by caching results for subproblems.
If the target amount is sum then we may need answers for all amounts from 0 up to sum in this form-
dp[i]= minimum coins required to get amount i
So, we need a 1-D array having length equal to the sum+1. This array is initialized with -1 as initial value to indicate no value is stored yet.
public class MinCoinSum {
public static void main(String[] args) {
int coins[] = {9, 6, 5, 1};
int sum = 101;
int[] dp = new int[sum+1];
Arrays.fill(dp, -1);
int c = minCoinsNeeded(coins, sum, dp);
System.out.println("Coins needed- " + c);
}
private static int minCoinsNeeded(int[] coins, int sum, int[] dp) {
if(sum == 0) {
return 0;
}
// value already stored, so return that value
if(dp[sum] != -1) {
return dp[sum];
}
int count = Integer.MAX_VALUE;
int res = 0;
// Go through all the coins
for (int coin : coins) {
// if current coin can be used to get the final amount
if(sum - coin >= 0) {
// recursively find the minimum coins for the remaining amount
res = minCoinsNeeded(coins, sum - coin, dp);
if(res != -1) {
count = Math.min(count, res+1);
}
}
}
// Store result in array
dp[sum] = (count == Integer.MAX_VALUE) ? -1 : count;
return dp[sum];
}
}
Output
Coins needed- 12
Time and space complexity with this approach
If amount is n and the number of coins is c then the space complexity is O(n X c). As there are n subproblems and c checks for each subproblem.
Space needed is O(n+1) for dp array and O(n) for recursion stack so the overall space complexity is O(n).
3. With tabulation (Bottom-up) approach
With tabulation form, to write logic for minimum number of coins to get the sum, iterative logic is used not recursive which in itself is an optimization. This is also called bottom-up approach as we build solutions for all amounts starting from 0 going up all the way to given sum.
A dp array of length equal to sum+1 is needed as we go through amount 0..sum.
All entries of dp should be initialized to a large number (at least greater than the sum). The value of dp[0] is equal to 0 (zero coins needed for amount 0). The logic for solution is as given below.
- Iterate in an outer loop for the coins
- In the inner loop, for each amount i, check if using this coin improves the minimum count.
- Compare the scenario, if this coin is added which means dp[i – coin]+1 with current dp[i] and take the minimum.
public class MinCoinSum {
public static void main(String[] args) {
int coins[] = {9, 6, 5, 1};
int sum = 101;
int c1 = minNoOfCoins(coins, sum);
System.out.println("Coins needed- " + c1);
}
private static int minNoOfCoins(int[] coins, int sum) {
int[] dp = new int[sum+1];
// Integer.MAX_VALUE causes problem when 1 is added to it
//Arrays.fill(dp, Integer.MAX_VALUE);
Arrays.fill(dp, sum+1);
dp[0] = 0;
for(int coin : coins) {
for(int i = coin; i <= sum; i++) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
return dp[sum] > sum ? -1 : dp[sum];
}
}
Output
Output Coins needed- 12
Time and space complexity with this approach
If amount is n and the number of coins is c then, Outer loop runs for each coin i.e. c times. Inner loop runs for each amount up to sum i.e. n times.
Thus, the time complexity is O(n X c).
DP array of size sum + 1 is requires so the space complexity is O(n).
That's all for this topic Coin Change - Min Number of Coines Needed - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-