Coin Change: Minimum Number Of Coins

Deeksha
Last Updated: May 18, 2022
Difficulty Level :
EASY

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: 

2 3 5 

11

Output:  

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: 

2 3 5 

11

Output:  

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: 

2 3 5 

11

Output:  

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!!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think