The Coin Change Problem

Reading time: 30 minutes | Coding time: 10 minutes

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

• 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[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.

References/ Further reading

1. https://github.com/OpenGenus/cosmos/tree/master/code/dynamic_programming/src/coin_change