Coin Change Problem

Introduction to Coin Change Problem

The “coin change problem” expects a solution to find the minimum number of specific denomination coins required to sum up to a given value.

This problem can be categorized as a variation of the “knapsack problem”, and the solution can be optimized using the Dynamic Programming approach. So let’s get started!

Problem Statement

We are given a value N and an array of denominations (consider an infinite number of coins for each denomination type). We have to return the minimum number of coins required to sum up to the given value N and return -1 if no such combination is possible.

Mathematical Definition

In mathematics, let’s consider that our denominations are $D_1, D_2, D_3, …, D_n$. And we are allowed to use any number of each denomination.

Then the given value N can be derived as $N = Σ (X_i\text{.}D_i)$, where $X_i$ is a non-negative integer denoting the number of coins for each type of denomination used. $X_i$ can be zero since it is not necessary to use all types of denominations.

Now the problem statement expects to minimize the total number of coins, i.e., we need to minimize the term, $Σ X_i$. Here $Σ X_i$ refers to the total number of coins required to sum up the given value.

Input and Output

The input for Coin Change Problem will be an integer N which has to be changed with the denominations, and an integer array which denotes the denominations.

The output should be an integer that indicates the minimum number of coins. Return -1 if no such combination is possible.

Example

Let’s consider a few sample cases.

Sample Case: 1

Input :

N=13, coins={1, 2, 6, 7, 9}

Output :

2

Sample Case : 2

Input :

N=7, coins={2, 4, 6}

Output :

-1

Example Explanation

Consider sample case 1.

As per the denominations, we initially think of using the denomination with the highest value to reduce the number of coins but in that case, we need 3 coins $(9, 2, 2)$. But the given value can be summed up using only 2 coins with the combination $(6, 7)$.

Now consider sample case 2.

As per the denominations, there are no such combinations that sum up to 7, so our output should be -1.

Approach – 1 : Simple & Slow Approach – Recursive Approach

The idea is to go through all the combinations of coins that sum up to the given value and maintain a global variable to compare and store the minimum number of coins. We can go with a recursive solution to implement this approach.

Algorithm :

• Consider a function minCoins(integer N, integer[] coins)
• The function has to terminate and return 0 if $N=0$ since the minimum number of coins required to fetch the sum 0 is 0 coins.
• Else if $N>0$, coinsRequired = minimum of all $(1 +$ minCoins$(N – D_i,$ coins$))$, for all the denominations $D_i$, and we have to return the coinsRequired.

When N is more significant than zero, we initially assume the current denomination is the part of the combination which sums up the given value. And this recursive call will further make calls with other denominations.

This recursion tree stops once we hit the base case $N=0$ (the combination we followed sums up to the given value), we then compare the length of the coin combination. Or the recursion tree breaks if $N<0$, where our combination sum exceeds the required.

Implementation

Java implementation :

public class Main {

  int minCoins(int C[], int l, int N) {
    if (N == 0) return 0; //base case
    int coinsRequired = Integer.MAX_VALUE;
    for (int i = 0; i < l; i++) { //looping over all the denomminations
      if (C[i] <= N) { //checking if current denomination is less than given value
        int curr = minCoins(C, l, N - C[i]);
        /*
                checking if any combinations exist with the current denomination
                and the length of the combination is less than the coins required
                */
        if (
          curr != Integer.MAX_VALUE && curr + 1 < coinsRequired
        ) coinsRequired = curr + 1; //updating the result with the minimum number
      }
    }
    return coinsRequired;
  }

  int coinChange(int[] C, int l, int N) { //wrapper method to handle -1 case
    int coinsRequired = minCoins(C, l, N);
    if (coinsRequired == Integer.MAX_VALUE) return -1;
    return coinsRequired;
  }

  public static void main(String[] args) {
    int[] coins = new int[] { 2, 6, 4 }; //denominations
    int N = 12; //given value N
    int l = coins.length; //number of denominations
    Main m = new Main();
    int coinsRequired = m.coinChange(coins, l, N);
    if (coinsRequired == -1) {
      System.out.println(
        "Given value cannot be exchanged with available denominations"
      );
    } else System.out.println("Minimum coins required is " + coinsRequired);
  }
}

C++ implementation :

#include<bits/stdc++.h>

using namespace std;

int minCoins(int C[], int l, int N){
    if(N == 0) //base case
        return 0;
    int coinsRequired = INT_MAX;
    for(int i = 0; i<l; i++){ //looping over all the denomminations
        if(C[i] <= N){ //checking if current denomination is less than given value
            int curr = minCoins(C, l, N-C[i]);
            /*
            checking if any combinations exist with the current denomination
            and the length of the combination is less than coinsRequired
            */
            if(curr != INT_MAX && curr + 1 < coinsRequired)
                coinsRequired = curr + 1; //updating the result with the minimum number
        }
    }
    return coinsRequired;
}

int coinChange(int C[], int l, int N){ //wrapper method to handle -1 case
    int coinsRequired = minCoins(C, l, N);
    if(coinsRequired == INT_MAX)
        return -1;
    return coinsRequired;
}

int main()
{
    int coins[] = {2,6,4}; //denominations
    int N = 12; //given value N
    int l = sizeof(coins)/sizeof(coins[0]); //number of denominations
    int coinsRequired = coinChange(coins, l, N);
    if(coinsRequired == -1)
        cout<< "Given value cannot be exchanged with available denominations";
    else
        cout<<"Minimum coins required is "<<coinsRequired;
    return 0;
}

Python implementation :

import sys

def minCoins(C, l, N):
if(N == 0): #base case
return 0
coinsRequired = sys.maxsize
for i in range(0, l): #looping over all the denomminations
if(C[i] <= N): #checking if current denomination is less than given value
curr = minCoins(C, l, N-C[i])
'''
checking if any combinations exists with the current denomination
and the length of the combination is less than coinsRequired
'''
if(curr != sys.maxsize and curr + 1 < coinsRequired):
coinsRequired = curr + 1 #updating the result with the minimum number
return coinsRequired

def coinChange(C, l, N): #wrapper method to handle -1 case
coinsRequired = minCoins(C, l, N)
if(coinsRequired == sys.maxsize):
return -1
return coinsRequired

Driver Problem

coins = [2,6,4] #denominations
N = 12 #given value N
l = len(coins) #number of denominations
coinsRequired = coinChange(coins, l, N)
if(coinsRequired == -1):
    print("Given value cannot be exchanged with available denominations")
else:
    print("Minimum coins required is",coinsRequired)

Output :

Minimum number of coins required is 2

In the above implementations,

• With each denomination, we check for the condition $N>=C[i]$ to confirm if we don’t fall in the case $N<0$.
• Each new recursive call itself is a new problem with denominations C and required value $N-C[i]$ which further makes other recursive calls.

Complexity Analysis

Time Complexity :

The above algorithm will make a recursive call for every denomination $D_i<=N$ and in the worst case, when all the denominations are less than the required value there will be $l$ recursive calls.

This case implies that the first layer of the recursive tree will have $l$ nodes in the worst case. Similarly, $l^2$ nodes in the second lever, $l^3$ nodes in the third layer, and so on. It gives us the total number of recursive calls equal to $(l^N – 1)/(l – 1)$. So the worst-case time complexity is equivalent to $O(l^N)$.

Space Complexity :

This approach doesn’t need any auxilary space, but it maintains a recusion stack internally.

If we consider the recursion tree, there is a repetition of a few sub-trees. Can we skip such recursive calls ?

Approach – 2 : Timely & Efficient Approach – Dynamic Programming Using Recursion

The idea is to note down the result of a subproblem, such that if the same subproblem is encountered, then the stored value can be utilized. This will avoid repetitive computation of overlapping subproblems.

The whole algorithm will be almost similar to the earlier recursive approach with an addition of a $l * N$ matrix to store the results.

Algorithm :

• Consider a function coinChange(integer N, integer[] coins, integer dp[])
• Initialize the integer dp[] array with -1.
• The function has to terminate and return 0 if $N=0$ since the minimum number of coins required to fetch the sum 0 is 0 coins.
• Else if $N>0$, check if $dp[N]!=-1$, then coinsRequired $= dp[N]$. Else for all the denominations $D_i$, coinsRequired = minimum of all $(1+$minCoins$(N-D_i,$ coins$) )$. Then we have to store and return the coinsRequired.

Implementation

Java implementation :

import java.util.*;

public class Main {

  int minCoins(int C[], int l, int N, int[] dp) {
    if (dp[N] != -1) return dp[N]; //if the subproblem is already visited //return the stored result

    int coinsRequired = Integer.MAX_VALUE;
    for (int i = 0; i < l; i++) { //looping over all the denominations
      if (C[i] <= N) { //checking if current denomination is less than given value
        int curr = minCoins(C, l, N - C[i], dp);
        /*
                checking if any combinations exists with the current denomination
                and the length of the combination is less than coinsRequired
                */
        if (
          curr != Integer.MAX_VALUE && curr + 1 < coinsRequired
        ) coinsRequired = curr + 1; //updating the result with the minimum number
      }
    }
    dp[N] = coinsRequired; //storing the result of current subproblem
    return coinsRequired;
  }

  int coinChange(int[] C, int l, int N, int[] dp) { //wrapper method to handle -1 case
    int coinsRequired = minCoins(C, l, N, dp);
    if (coinsRequired == Integer.MAX_VALUE) return -1;
    return coinsRequired;
  }

  public static void main(String[] args) {
    int[] coins = new int[] { 1, 2, 6, 4, 8, 10 }; //denominations
    int N = 13; //given value N
    int l = coins.length; //number of denominations

    int[] dp = new int[N + 1]; //DP array to store results of subproblems

    /*
        Initially filling the whole dp array with -1
        Indicates that all the subproblems are unvisited
        */
    Arrays.fill(dp, -1);
    //base case
    dp[0] = 0;
    Main m = new Main();
    int coinsRequired = m.coinChange(coins, l, N, dp);

    if (coinsRequired == -1) {
      System.out.println(
        "Given value cannot be exchanged with available denominations"
      );
    } else System.out.println("Minimum coins required is " + coinsRequired);
  }
}

C++ implementation :

#include<bits/stdc++.h>

using namespace std;

int minCoins(int C[], int l, int N, int dp[]){

    if(dp[N]!=-1) //if the subproblem is already visited
        return dp[N]; //return the stored result

    int coinsRequired = INT_MAX;
    for(int i = 0; i<l; i++){ //looping over all the denominations
        if(C[i] <= N){ //checking if current denomination is less than given value
            int curr = minCoins(C, l, N-C[i], dp);
            /*
            checking if any combinations exists with the current denomination
            and the length of the combination is less than coinsRequired
            */
            if(curr != INT_MAX && curr + 1 < coinsRequired)
                coinsRequired = curr + 1; //updating the result with the minimum number
      }
   }
    dp[N]=coinsRequired; //storing the result of current subproblem
    return coinsRequired;
}

int coinChange(int C[], int l, int N, int dp[]){ //wrapper method to handle -1 case
    int coinsRequired = minCoins(C, l, N, dp);
    if(coinsRequired == INT_MAX)
        return -1;
    return coinsRequired;
}

int main()
{
    int coins[] = {1, 2, 6, 4, 8, 10}; //denominations
	int N = 13; //given value N
	int l = sizeof(coins)/sizeof(coins[0]); //number of denominations

	int dp[N+1]; //DP array to store results of subproblems

    /*
    Initially filling the whole dp array with -1
    Indicates that all the subproblems are unvisited
    */
    fill(dp, dp+N+1, -1);

    //base case
    dp[0]=0;

    int coinsRequired = coinChange(coins, l, N, dp);

    if(coinsRequired == -1){
        cout<<"Given value cannot be exchanged with available denominations";
    }
    else
	    cout<<"Minimum coins required is "<<coinsRequired;

    return 0;
}

Python implementation :

import sys

def minCoins(C, l, N, dp):
    if(dp[N]!=-1): #if the subproblem is already visited
        return dp[N]; #return the stored result

    coinsRequired = sys.maxsize
    for i in range(0, l): #looping over all the denomminations
        if(C[i] <= N): #checking if current denomination is less than given value
            curr = minCoins(C, l, N-C[i], dp)
            '''
            checking if any combinations exists with the current denomination
            and the length of the combination is less than coinsRequired
            '''
            if(curr != sys.maxsize and curr + 1 < coinsRequired):
                coinsRequired = curr + 1 #updating the result with the minimum number
    dp[N] = coinsRequired
    return coinsRequired


def coinChange(C, l, N, dp): #wrapper method to handle -1 case
    coinsRequired = minCoins(C, l, N, dp)
    if(coinsRequired == sys.maxsize):
        return -1
    return coinsRequired


#Driver program

coins = [1, 2, 6, 4, 8, 10] #denominations
N = 13 #given value N
l = len(coins) #number of denominations

dp=[] #DP array to store results of subproblems
'''
Initially filling the whole dp array with -1
Indicates that all the subproblems are unvisited
'''
dp=[-1 for i in range(N+1)]

#base case
dp[0]=0;

coinsRequired = coinChange(coins, l, N, dp)
if(coinsRequired == -1):
    print("Given value cannot be exchanged with available denominations")
else:
    print("Minimum coins required is",coinsRequired)

Output :

Minimum coins required is 3

Complexity Analysis

Time Complexity :

In the worst case we’ll make a recursive call for all the values from 1 to N, i.e., minCoins$(N,$ coins$)$, minCoins$(N-1,$ coins$)$, minCoins$(N-2,$ coins$)…$, minCoins$(0,$ coins$)$. And each recursive call has to loop over all denominations to find the minimum coins, so $l$ x constant time. (constant time since we are memoizing the results of recursive calls).

So the time complexity of this algorithm will be $O(N . l)$.

Space Complexity :

This approach requires an auxiliary array of size N+1. So the space complexity will be $O(N)$.

Also, this approach will maintain a recursion stack of size N in the worst case.

Efficient Approach in Space – Iterative Approach with Space Complexity O(N)

The idea is to skip the repetitive computation by avoiding overlapping subproblems. In the previous approaches, we’ve made a recursive call to find the minimum coins required, the algorithm will be similar, but the DP table is filled iteratively.

In this approach, we’ll start solving the smaller problems first. Such that their results will be used in deriving the required solution. This approach is referred to as the bottom-up approach, where we start from the base case.
In the recursive and memoization approach, the recurrence relation we used is,
minCoins$(N) =$ min$(1 +$ minCoins$(N – D_i))$ for all the denominations
In the bottom-up approach(tabulation) the recurrence relation will be,
$dp[i] =$ min$(1 + dp[i – D_i])$ for all the denominations $D_i$, and i loops from 0 to N.

Algorithm :

• Consider a function coinChange(integer N, integer[] coins)
• Initialize the integer $dp[]$ array with -1.
• Update the $dp[0] = 1$ (base case)
• Loop the problem(i) from the base case $1$ to $N$
• Loop over all the denominations $D_i$
• Update the $dp[i] =$ minimum$(1 + dp[i – D_i])$
• Return $dp[N]$

Implementation :

Java implementation :

import java.util.*;

class Main {

  int minCoins(int coins[], int l, int N) {
    //dp array to store the results of each subproblem
    int dp[] = new int[N + 1];

    /*
        Initially filling the whole array with integer maximum
        Assuming that no combination of denominations exists for each subproblem
        */
    Arrays.fill(dp, Integer.MAX_VALUE);

    dp[0] = 0; //base case

    /*
        Finding the result for each subproblem iteratively in a top-down manner
        */
    for (int i = 1; i <= N; i++) { //looping over each subproblem
      for (int j = 0; j < l; j++) { //looping over each denomination
        if (coins[j] <= i) { //checking if current denominations is less than given value
          int curr = dp[i - coins[j]];
          /*
                    checking if any combination exists with the current denomination
                    and the length of the combination is less than coinsRequired
                    */
          if (curr != Integer.MAX_VALUE && curr + 1 < dp[i]) dp[i] = curr + 1; //updating the result with the minimum number
        }
      }
    }

    //dp[N] will be unchanged if no combination sums up to the given value
    if (dp[N] == Integer.MAX_VALUE) return -1;

    return dp[N];
  }

  public static void main(String[] args) {
    int[] coins = new int[] {1, 2, 6, 4, 8, 10 }; //denominations
    int N = 13; //given value N
    int l = coins.length; //number of denominations

    Main m = new Main();
    int coinsRequired = m.minCoins(coins, l, N);

    if (coinsRequired == -1) {
      System.out.println(
        "Given value cannot be exchanged with available denominations"
      );
    } else System.out.println("Minimum coins required is " + coinsRequired);
  }
}

C++ implementation :

#include<bits/stdc++.h>

using namespace std;

int minCoins(int coins[], int l, int N){

    //dp array to store the results of each subproblem
    int dp[N+1];

    /*
    Initially filling the whole array with integer maximum
    Assuming that no combination of denominations exists for each subproblem
    */
    fill(dp, dp+N+1, INT_MAX);

    dp[0] = 0; //base case

    /*
    Finding the result for each subproblem iteratively in a top-down manner
    */
    for (int i = 1; i <= N; i++){ //looping over each subproblem
        for (int j = 0; j < l; j++){ //looping over each denomination
            if (coins[j] <= i){ //checking if current denominations is less than given value
                int curr = dp[i - coins[j]];
                /*
                checking if any combination exists with the current denomination
                and the length of the combination is less than coinsRequired
                */
                if (curr != INT_MAX && curr + 1 < dp[i])
                    dp[i] = curr + 1; //updating the result with the minimum number
            }
        }
    }

    //dp[N] will be unchanged if no combination sums up to the given value
    if(dp[N]==INT_MAX)
        return -1;

    return dp[N];

}

int main()
{
    int coins[] = {1, 2,6,4,8,10}; //denominations
	int N = 13; //given value N
	int l = sizeof(coins)/sizeof(coins[0]); //number of denominations

    int coinsRequired = minCoins(coins, l, N);

    if(coinsRequired == -1){
        cout<<"Given value cannot be exchanged with available denominations";
    }
    else
        cout<<"Minimum coins required is "<<coinsRequired;

    return 0;
}

Python implementation :

import sys

def minCoins(coins, l, N):

    #dp array to store the results of each subproblem
    dp=[]

    '''
    Initially filling the whole array with integer maximum
    Assuming that no combination of denominations exists for each subproblem
    '''
    dp = [sys.maxsize for i in range(N+1)]

    dp[0] = 0 #base case

    '''
    Finding the result for each subproblem iteratively in a top-down manner
    '''
    for i in range(1,N+1): #looping over each subproblem
        for j in range(0,l): #looping over each denomination
            if (coins[j] <= i): #checking if current denominations is less than given value
                curr = dp[i - coins[j]]
                '''
                checking if any combination exists with the current denomination
                and the length of the combination is less than coinsRequired
                '''
                if (curr != sys.maxsize and curr + 1 < dp[i]):
                    dp[i] = curr + 1 #updating the result with the minimum number

    #dp[N] will be unchanged if no combination sums up to the given value
    if(dp[N]==sys.maxsize):
        return -1

    return dp[N]

#Driver program

coins = [1,2,4,6,8,10] #denominations
N = 13 #given value N
l = len(coins) #number of denominations

coinsRequired = minCoins(coins, l, N)

if(coinsRequired == -1):
    print("Given value cannot be exchanged with available denominations")
else:
    print("Minimum coins required is",coinsRequired)

Output :

Minimum coins required is 3

Remember, we are finding the minimum coins required for each smaller problem with all denominations, but not each denomination with all smaller problems. So the outer loop should be 1 to N, and the inner loop should loop over the coins.

Complexity Analysis

Time Complexity :

The outer loop will loop $N$ times, and the inner loop will loop $l$ times. So, the time complexity for this approach will be $O(N*l)$.

Space Complexity :

This approach requires an auxiliary array of size $N+1$. So the space complexity will be $O(N)$.
Both the tabulation and memoization have the same time complexity $O(N*l)$ and space complexity $O(N)$. But the memoization approach maintains a recursion stack internally.

Applications of Coin Change Problem

The algorithm for the coin change problem has applications in ticket vending machines, candy vending machines, etc.

Where the machine can dynamically update the availability of the denominations, and the algorithm will notify if the change is not available (return -1 case) or provide the difference with a minimum number of coins.

Conclusion

• The coin change problem seeks a solution that returns the minimum number of coins required to sum up to the given value.
• We are trying to minimize $Σ X_i$ while attaining $N = Σ X_i. D_i$
• The recursive approach checks the length of all the combinations which sum up to the given value and returns the minimum combination length.
• The memoization approach overcomes the overlapping subproblems issue by storing the result of recursive calls.
• The tabulation approach flows iteratively and overcomes the need for a recursion stack.
• The coin change problem has many applications because of its space and time efficiency.