Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

The coin change problem has a variant known as the minimum number of coins problem. The aim is to determine the smallest number of coins required to equal a particular value. Only coins from a specific array should be used.

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 coin change problem.

Problem Statement

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 clearly understand this Coin Change Problem.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Example

Suppose You are given an array of coins:

Now the amount you have to make is 11.

We can observe that there are multiple ways to make a total of 11 from given coin denominations.

So you can see that the minimum number of coins that will be used is 3 i.e. (5 + 5 + 1) or (5+3+3). 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 algorithm in steps for this coin change problem:

Algorithm

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.

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.

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

Dry Run

Just shown the glimpse of the recursion tree, hope you guys have understood the idea/logic behind the recursive calls

Implementation in C++

C++

C++

#include <bits/stdc++.h> using namespace std;

int coinChangeHelper(vector < int > & coins, int start,int amount) {

// Base Case if (start > coins.size()-1) { if (amount == 0) { return 0; } return -1; }

// If amount is negative if (amount < 0) { return -1; }

// Recursive calls int ans1 = coinChangeHelper(coins, start, amount - coins[start]); int ans2 = coinChangeHelper(coins, start + 1, amount);

// 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, amount); }

int main() { vector < int > coins={1,3,5};

int amount=11;

// Calling the function cout << coinChange(coins, amount); return 0; }

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 is present in that array already; then, we can escape from making the same call again. This technique is called memoisation.

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 the results of previous calls. The row of this 2D array will signify the size of the coins array, and the column will represent amounts.

Please try to code this approach yourself; you will only 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:

Implementation in C++

C++

C++

#include <bits/stdc++.h> using namespace std;

int coinChangeHelper(vector < int > & coins, int start,int amount, int ** mem) {

// Base Case if (start > coins.size()-1) { 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]; }

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, amount, mem); }

int main() { vector < int > coins={1,3,5};

int amount=11;

// Calling the function cout << coinChange(coins, amount); return 0; }

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 Dynamic Programming (Bottom Up Approach)

To solve this problem using Dynamic Programming, we have to take a 2-D array where:

Rows will signify the size of the array

Columns will signify the amounts.

Now let’s understand this approach better with the help of the steps:

Algorithm

Make a 2D array with N + 1 rows and amount + 1 columns because the amount can also be zero. Here N is the size of coins array.

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.

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.

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.

For the 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 have your answer placed at dp[N][amount]. Yes! That simple it is. Now try coding it out.

Implementation in C++

C++

C++

#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 Then we can include the current coin in our ans. */ 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() { vector < int > coins={1,3,5};

int amount=11;

// Calling the function cout << coinChange(coins, amount); return 0; }

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.

Approach 4: Using Optimized DP

In the previous dp approach, we can observe that the answer is only dependent on the previous dp array (dp[i][j] is dependent on the value of dp[i-1][j]). Thus we can reduce our answer to a single dp and optimise the space complexity.

Algorithm

Initialize a dp array of “Amount+1” size with values equal to the maximum number of coins possible to make the current amount (initialize it with “Amount”)

Dp[i] represents minimum number of ways to make the ‘i’ amount.

Initialize dp[0]=0.

For each coin in the array, check all possible amounts where the coin can occur.

This way, the level wise update the number of ways to reach the ith amount.

Implementation in C++

C++

C++

#include <bits/stdc++.h> using namespace std;

int coinChange(vector < int > & coins, int amount) { int n = coins.size();

//checking if amount is already 0. Then return 0. if(amount==0) return 0;

/* 1-D array for storing the results and initializing it to maximum number of coins possible. */

vector<int> dp(amount+1,amount+1);

// dp[i] stores the result of the number of coins needed to make "i" amount.

/* initializing dp[0]=0 because if amount is zero there is only 1 way to get 0 amount and that is by taking none of the available coins. */

dp[0]=0; // Traversing the the array for (int i = 0; i < n; i++) {

/* for each coin in the array, checking all possible amounts where the coin can occur. */ for (int j = coins[i]; j <= amount; j++) { if(j-coins[i]>=0)

//taking minimum of all possible answers. dp[j]=min(dp[j],1+dp[j-coins[i]]); } }

return dp[amount]; }

int main() { vector < int > coins={1,3,5};

int amount=11;

// Calling the function cout << coinChange(coins, amount); return 0; }

Output

3

Complexity Analysis

Time Complexity: O(N * Amount) where ‘N’ refers to the size of the array.

Space Complexity: O(Amount). Here we are not using any additional data structure, we are using only an array of “Amount” size to store the results.

Frequently Asked Questions

What is the minimum coin problem in Java?

Finding the least number of coins required to make a certain amount of money with a given set of coin denominations is known as the minimum coin problem in Java. This problem is frequently handled using dynamic programming or greedy algorithms.

Why do I need to opt for DP and memoized code when I have already solved this question using recursion?

In the recursion solution, you are making overlapping recursive calls which are costing you in the form of exponential time complexity.

What is the time complexity of the minimum coin change problem?

The time complexity of the minimum coin change problem is 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.

What are the applications of the coin change problem?

The coin change problem has numerous applications, including currency exchange, vending machines, and financial resource allocation optimization. It also forms the basis for the solution of scheduling and knapsack problems and is used in algorithm creation.

Conclusion

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 a manner that starts from brute force and then keep optimizing the code.