# The Coin Change Problem

#### algorithm dynamic programming 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=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. 