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 :

Output :

Sample Case : 2

Input :

Output :

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 :

C++ implementation :

Python implementation :

Output :

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 :

C++ implementation :

Python implementation :

Output :

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 :

C++ implementation :

Python implementation :

Output :

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)$.

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.