Coin Change: Minimum Number Of Coins
Introduction
In this blog, we will discuss a problem Coin Change: Minimum number of coins. This is the most important question which is asked frequently in interviews. Let’s understand the problem statement of this coin change problem: You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money. You have to 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, you will return -1. You may assume that you have an infinite number of each kind of coin.
Let’s see an example to get a clear idea of this problem coin change:-
You are given an array of coins:
1 | 2 | 5 |
Now the amount you have to make is 11. So you can see that the minimum number of coins that will be used are 3 i.e 5 + 5 + 1. Hence you have to return 3 as output.
Since you have understood the problem clearly. Now is the time to move towards the solution:-
Approach#1: Using Recursion
On each element in the coins array, you have two choices whether it will be included to reach the amount or it will not be included. Remember whenever you have choices, that’s a clear indication that the problem can be solved using recursion.
Let’s see the approach in steps for this coin change problem:
Step1: We will decide on a base case first. The base case will be that suppose the size of the ‘coins’ array is zero and the amount you have to make is also zero, then you will return 0 because to make zero amount zero coins are sufficient else we will return -1.
Step 2: Now on each coin in coins array we will decide:
That this coin will be used in making the amount and will do amount - coins[i]
That this coin will not be used in making the amount and will do start + 1.
Step 3. Now add 1 in the first recursive call since you decided in that call that you are taking that coin and return the minimum of the answers received by recursive calls.
Now let’s see that how it looks in code
C++ code
#include <bits/stdc++.h>
using namespace std;
int coinChangeHelper(vector < int > & coins, int start, int end, int amount) {
// Base Case
if (start > end) {
if (amount == 0) {
return 0;
}
return -1;
}
// If amount is negative
if (amount < 0) {
return -1;
}
// Recursive calls
int ans1 = coinChangeHelper(coins, start, end, amount - coins[start]);
int ans2 = coinChangeHelper(coins, start + 1, end, amount);
if (ans1 != -1 && ans2 != -1) {
return min(ans1 + 1, ans2);
}
// If we cannot achieve that amount through recursive call 1
if (ans1 == -1) {
return ans2;
}
// If we cannot achieve that amount through recursive call 2
if (ans2 == -1) {
return (ans1 + 1);
}
return -1;
}
int coinChange(vector < int > & coins, int amount) {
return coinChangeHelper(coins, 0, coins.size() - 1, amount);
}
int main() {
int n;
cin >> n;
vector < int > coins;
for (int i = 0; i < n; i++) {
int elem;
cin >> elem;
coins.push_back(elem);
}
int amount;
cin >> amount;
// Calling the function
cout << coinChange(coins, amount);
return 0;
}
Python Code
def main():
# No of denominations
n = int(input())
# denominations
denominations = list(map(int, input().split()))
# amount
target = int(input())
# Recursive approach
def coinCombinations(denominations, idx, target):
# Base Case
if target == 0: return 1
ways = 0
for i in range(idx, len(denominations)):
# Counting ways if i-th denomination cam be included
if target - denominations[i] >=0:
ways += coinCombinations(denominations, i, target-denominations[i])
return ways
res = coinCombinations(denominations, 0, target)
print("Total combinations are", res)
main()
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter number of denominations");
int n = s.nextInt();
int[] denominations = new int[n];
System.out.println("Enter denominations");
for (int i = 0; i < n; i++) denominations[i] = s.nextInt();
System.out.println("Enter amount");
int target = s.nextInt();
int ways = coinCombinations(denominations, 0, target);
System.out.print("Coin change combinations are: ");
System.out.println(ways);
}
// Recursive approach
public static int coinCombinations(int[] denominations, int idx, int target){
// Base Case
if (target == 0) return 1;
int ways = 0;
for (int i = idx; i < denominations.length; i++){
// Counting ways if i-th denomination cam be included
if (target - denominations[i] >=0 )
ways += coinCombinations(denominations, i, target-denominations[i]);
}
return ways;
}
}
Input:
3
2 3 5
11
Output:
3
Complexity Analysis
Time Complexity: O(2 ^ N) where ‘N’ refers to the size of coins array. On each element, we have two choices whether to take or not include it, which is giving us exponential time complexity.
Space Complexity: O(N) where ‘N’ refers to the size of coins array. Due to recursion, we are consuming this space in the recursion call stack.
Now you can see that in this approach of the coin change, we are making overlapping recursive calls that are costing us time Complexity. So to solve this problem, we will store the result of each recursive call in an array, and before making a new recursive call, we will check if the answer of that recursive call will be present in that array already, then we can escape from making the same call again.
Approach#2: Using Memoization
All the steps will be the same as approach 1; the only difference is that here we will make a 2D array to store results of previous calls. The row of this 2D array will signify the size of the coins array, and the column will represent amounts.
Now please try to code this approach by yourself; only then you will gain confidence for your interviews.
Okay, I hope you have tried coding it on your own. Now let’s see the way I have code:
C++ code
#include <bits/stdc++.h>
using namespace std;
int coinChangeHelper(vector < int > & coins, int start, int end, int amount, int ** mem) {
// Base Case
if (start > end) {
if (amount == 0) {
return 0;
}
return -1;
}
// If amount is negative
if (amount < 0) {
return -1;
}
// If result of that recursive call already present
if (mem[start][amount] != -1) {
return mem[start][amount];
}
// Recursive calls
int ans1 = coinChangeHelper(coins, start, end, amount - coins[start], mem);
int ans2 = coinChangeHelper(coins, start + 1, end, amount, mem);
if (ans1 != -1 && ans2 != -1) {
mem[start][amount] = min(ans1 + 1, ans2);
return mem[start][amount];
}
if (ans1 == -1) {
mem[start][amount] = ans2;
return mem[start][amount];
}
if (ans2 == -1) {
mem[start][amount] = (ans1 + 1);
return mem[start][amount];
}
return -1;
}
int coinChange(vector < int > & coins, int amount) {
// Forming the array for storing the results of the recursive calls
int ** mem = new int * [coins.size()];
for (int i = 0; i < coins.size(); i++) {
mem[i] = new int[amount + 1];
for (int j = 0; j <= amount; j++) {
mem[i][j] = -1;
}
}
return coinChangeHelper(coins, 0, coins.size() - 1, amount, mem);
}
int main() {
int n;
cin >> n;
vector < int > coins;
for (int i = 0; i < n; i++) {
int elem;
cin >> elem;
coins.push_back(elem);
}
int amount;
cin >> amount;
//calling the function
cout << coinChange(coins, amount);
return 0;
}
Python Code
def main():
# No of denominations
n = int(input())
# denominations
denominations = list(map(int, input().split()))
# amount
target = int(input())
# Top Down DP approach
def coinCombinations(denominations, idx, target, dp):
# Base Case
if target == 0: return 1
# LookUp in Dp Array
if dp[idx][target] != 0: return dp[idx][target]
ways = 0
for i in range(idx, len(denominations)):
# Counting ways if i-th denomination can be included
if target - denominations[i] >=0:
ways += coinCombinations(denominations, i, target-denominations[i], dp);
dp[idx][target] = ways
return ways
# Forming Dp Array
dp = [[0 for j in range(target+1)] for i in range(len(denominations))]
ways = coinCombinations(denominations, 0, target, dp)
print("Coin change combinations are: ", ways)
main()
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter number of denominations");
int n = s.nextInt();
int[] denominations = new int[n];
System.out.println("Enter denominations");
for (int i = 0; i < n; i++)
{
denominations[i] = s.nextInt();
}
System.out.println("Enter amount");
int target = s.nextInt();
// Forming Dp Array
int[][] dp = new int[denominations.length][target + 1];
int ways = coinCombinations(denominations, 0, target, dp);
System.out.print("Coin change combinations are: ");
System.out.println(ways);
}
// Top Down DP approach
public static int coinCombinations(int[] denominations, int idx, int target, int[][] dp){
// Base Case
if (target == 0) return 1;
// LookUp in Dp Array
if (dp[idx][target] != 0) return dp[idx][target];
int ways = 0;
for (int i = idx; i < denominations.length; i++){
// Counting ways if i-th denomination can be included
if (target - denominations[i] >=0 )
ways += coinCombinations(denominations, i, target-denominations[i], dp);
}
return dp[idx][target] = ways;
}
}
Input:
3
2 3 5
11
Output:
3
Complexity Analysis
Time Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. Here we are visiting a 2-D array of size N * A just once that’s why we are arriving at this time complexity.
Space Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. We are consuming this space as a 2-D array to store the results of recursive calls.
Now we have discussed the recursive and memoized code. So, this is the time to move towards a Dynamic Programming solution.
Approach#3: Using DP (Bottom Up Approach)
For solving this problem using Dynamic Programming we have to take a 2-D array where :
- Rows will be signifying the size of the array
- Columns will be signifying the amounts.
Now let’s understand this approach better with the help of steps:
Step 1: Make a 2D array having N + 1 rows and amount + 1 columns because the amount can be zero also.
Step 2: Now see the case when we have a zero-sized array and have to return a minimum number of coins for zero amount. Then the answer should be 0. Right? So dp[0][0] = 0.
Step 3: Now suppose we have a zero-sized array and have to make an amount greater than 0 then there is no way to return a minimum no of coins. So just put -1 in these cases.
Step 4. One more case will be that suppose you have an array of size greater than zero but the amount we have to make is 0 then obviously the output will be 0.
Step 5. For rest of the cases we have to put a minimum of the two cases:
- When we are taking the current coin in our amount
- When we are not taking the current coin in our amount.
After these five steps, you will be having your answer placed at dp[N][amount]. Yes! That simple it is. Now try coding it out.
C++ code
#include <bits/stdc++.h>
using namespace std;
int coinChange(vector < int > & coins, int amount) {
int n = coins.size();
// 2-D array for storing the results
int ** dp = new int * [n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = new int[amount + 1];
}
// Traversing the 2-D dp array
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
// If size of the array is zero and amount is also zero
if (i == 0 && j == 0) {
dp[i][j] = 0;
}
// If size of the array is zero
else if (i == 0) {
dp[i][j] = -1;
}
// If the amount is zero
else if (j == 0) {
dp[i][j] = 0;
}
else {
// If the value of current coin is less than the amount
if (j - coins[i - 1] >= 0) {
if (dp[i][j - coins[i - 1]] != -1 && dp[i - 1][j] != -1)
dp[i][j] = min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j]);
// If we can't take the current coin for making our amount
else if (dp[i][j - coins[i - 1]] == -1) {
dp[i][j] = dp[i - 1][j];
}
else if (dp[i - 1][j] == -1) {
dp[i][j] = (dp[i][j - coins[i - 1]] + 1);
}
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[n][amount];
}
int main() {
int n;
cin >> n;
vector < int > coins;
for (int i = 0; i < n; i++) {
int elem;
cin >> elem;
coins.push_back(elem);
}
int amount;
cin >> amount;
// Calling the function
cout << coinChange(coins, amount);
return 0;
}
Python Code
def main():
# No of denominations
n = int(input())
# denominations
denominations = list(map(int, input().split()))
# amount
target = int(input())
# Bottom Up DP approach
def coinCombinationsDp(denominations, target):
# Forming dp array
dp = [0 for i in range(target + 1)]
# 0 amount could be get in 1 way (i.e. not selecting any coin)
dp[0] = 1;
# Counting coin change combinations
for i in range(len(denominations)):
for j in range(1, len(dp)):
if j - denominations[i] < 0: continue
dp[j] += dp[j- denominations[i]]
print("Coin change combinations are: ", dp[len(dp) - 1])
coinCombinationsDp(denominations, target)
main()
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter number of denominations");
int n = s.nextInt();
int[] denominations = new int[n];
System.out.println("Enter denominations");
for (int i = 0; i < n; i++) denominations[i] = s.nextInt();
System.out.println("Enter amount");
int target = s.nextInt();
coinCombinationsDp(denominations, target);
}
// Bottom Up DP approach
public static void coinCombinationsDp(int[] denominations, int target){
// Forming dp array
int[] dp = new int[target + 1];
/*
precompute
0 amount could be get in 1 way (i.e. not selecting any coin)
*/
dp[0] = 1;
// Counting coin change combinations
for (int i = 0; i < denominations.length; i++){
for (int j = 1; j < dp.length; j++){
if (j - denominations[i] < 0) continue;
dp[j] += dp[j- denominations[i]];
}
}
System.out.print("Coin change combinations are: ");
System.out.println(dp[dp.length - 1]);
}
}
Input:
3
2 3 5
11
Output:
3
Complexity Analysis
Time Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. Here we are visiting a 2-D array of size N * A just once that’s why we are arriving at this time complexity.
Space Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. We are consuming this space as a 2-D array to store the results of previous inputs.
Take a look at this video for proper implementation of code to understand it better.
Frequently Asked Questions
Ques 1. Why do I need to opt for DP and memoized code when I have already solved this question using recursion?
Ans 1. In the recursion solution, you are making overlapping recursive calls which are costing you in the form of exponential time complexity.
Ques 2. Can I write a solution for the problem of coin change in O(1) Space Complexity?
Ans 2. No! You can’t because in recursive code you need space for recursive call stacks and in DP code you need to consume space for storing previous results.
Key Takeaways:
In this blog, I have discussed all three approaches for the problem of coin change: Minimum number of coins. You can see that I keep optimizing my code so that I can eliminate overlapping recursive calls. Remember, in interviews; you are also expected to solve questions in this manner that starts from brute force and then keep optimizing the code. If you want to rock in your tech interviews, you have to practice a variety of questions, and let me share with you the CodeStudio platform where you can find questions asked in all big-tech giants.
Remember, positivity and knowledge are the only things in this world that increase exponentially on sharing. So, please do share this blog with your friends. Happy Coding!!
Comments
No comments yet
Be the first to share what you think