# The Coin Change Problem

#### Algorithms Dynamic Programming (DP) coin change problem Get FREE domain for 1st year and build your brand new site

Reading time: 30 minutes | Coding time: 10 minutes

The coin change problem is a problem with real life applications which can be solved efficiently using Dynamic Programming.

Given a set of coins \$S\$ with values \${ S1, S2, ..., Sm }\$,find the number of ways of making the change to a certain value \$N\$.There is an infinite quantity of coins and the order of the coins doesn't matter.
For example:
For \$S = {1, 2, 3}\$ and \$N = 4\$, the number of possibilities is 4, that are: \${1,1,1,1}\$, \${1,1,2}\$, \${2,2}\$ and \${1,3}\$. Note that the sets \${1,2,1}\$,\${2,1,1}\$ and \${3,1}\$ don't count to solution as they are permutations of the other ones.

### Algorithm

This is a classic dynamic programming problem. If you maintain an array of \$ways\$ change can be made from \$0\$ to \$n\$ , you can step through each denomination starting at its index and incrementing to the right, adding \$ways[index-coins[i]]\$ to each element \$ways[i]\$ to get a running total. Using the example from the problem statement, \$n=12\$ and \$coins=[1,2,5,10]\$, the steps are shown below. Note that there is \$1\$ way to give change for \$0\$ dollars. Initialize the array with a \$1\$ in the zero position, and zeros everywhere else. Here are the steps in computing the \$ways\$ array:

``````initial array:
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
0  1  2  3  4  5  6  7  8  9  10  11  12  <-- dollar amount
handling coin 1:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1]
handling coin 2:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5,  6,  6,  7]
handling coin 5:
[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13]
handling coin 10:
[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15]
15
``````

## Pseudocode

The pseudocode of Coin Change Problem is as follows:

1. initialize a new array for memoization of length n+1 where n is the number of which we want to find the number of different way of coin changes.
2. make memo=1 since there is only one way to give chage for 0 dollars
3. for each coin change available, iterate through the memoization array and add value of memo[index-coins[i]] to memo[index] for index from '1' to 'n'
4. return value of memo[n]

### Complexity

• Time complexity (in any case): `Θ(n*c)`
• Space complexity: `Θ(n)`

where

• n = number to find coin change
• c = number of coins available

### Implementation

``````import java.io.*;
import java.util.*;
public class Solution
{
static long ways(int n, int[] coins)
{
long memo[] = new long[n+1];
memo = 1;
for(int i = 0;i&lt;coins.length;i++)
{
for(int j = 1;j&lt;=n;j++)
{
if(j-coins[i]&gt;=0) memo[j]+=memo[j-coins[i]];
}
}
return memo[n];
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException
{
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm);
int m = Integer.parseInt(nm);
int[] coins = new int[m];
String[] coinsItems = scanner.nextLine().split(" ");
for (int i = 0; i &lt; m; i++)
{
int coinsItem = Integer.parseInt(coinsItems[i]);
coins[i] = coinsItem;
}
long res = ways(n, coins);
System.out.println(res);
scanner.close();
}
}
``````

### Applications

This algorithm can be used to distribute change i.e. In a soda pop vending machine that could accept bills and coins and dispense coins.
One example is, buying a 60 cent soda pop with a dollar. This leaves 40 cents change, or in the US, 1 quarter, 1 dime, and 1 nickel for least coin pay. If the nickel tube were empty though, the machine would dispense 4 dimes. 