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