Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach 1: Using Recursion
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.4.
C++
4.5.
Complexity Analysis
5.
Approach 2: Using Memoization
5.1.
Implementation in C++
5.2.
C++
5.3.
Complexity Analysis
6.
Approach 3: Using Dynamic Programming (Bottom Up Approach)
6.1.
Algorithm
6.2.
Implementation in C++
6.3.
C++
6.4.
Complexity Analysis
7.
Approach 4: Using Optimized DP
7.1.
Algorithm
7.2.
Implementation in C++
7.3.
C++
7.4.
Complexity Analysis
8.
Frequently Asked Questions
8.1.
What is the minimum coin problem in Java?
8.2.
Why do I need to opt for DP and memoized code when I have already solved this question using recursion? 
8.3.
What is the time complexity of the minimum coin change problem?
8.4.
What are the applications of the coin change problem?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Coin Change: Minimum Number Of Coins

Author Rhythm Jain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
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. 

minimum number of coins

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: 

Array

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. 

Possible Combinations

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

  1. 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.
     
  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.
       
  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

Dry Run

Recursion Tree

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 (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, 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.

Repeated subcases in recursion tree

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];
   }


   // Recursive calls
   int ans1 = coinChangeHelper(coins, start, amount - coins[start], mem);
   int ans2 = coinChangeHelper(coins, start + 1, 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, 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.

Check out this problem - Minimum Coin Change Problem 

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

  1. 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.
     
  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.
     
  3. 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.
     
  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.
     
  5. 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

  1. 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”)
     
  2. Dp[i] represents minimum number of ways to make the ‘i’ amount.
     
  3. Initialize dp[0]=0.
     
  4. For each coin in the array, check all possible amounts where the coin can occur. 
     
  5. 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. 

Recommended Problems:

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem DesignDSA C++etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass