# The Coin Change Problem

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[0]=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

- $n = number to find coin change$, $c = number of coins available$
- Time complexity (in any case):
**Θ(n*c)** - Space complexity:
**Θ(n)**

### Implementation

- Java

### Java

```
import java.io.*;
import java.util.*;
public class Solution
{
static long ways(int n, int[] coins)
{
long memo[] = new long[n+1];
memo[0] = 1;
for(int i = 0;i<coins.length;i++)
{
for(int j = 1;j<=n;j++)
{
if(j-coins[i]>=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[0]);
int m = Integer.parseInt(nm[1]);
int[] coins = new int[m];
String[] coinsItems = scanner.nextLine().split(" ");
for (int i = 0; i < 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.