Coin change problem

Tags: ,

Coin change problem

Given a number S and coins of values V = {V1,V2,V3, V4}. Find number of ways change can be made for S using these coins.We have infinite supply of these coins. Commonly, this problem is known as coin change problem.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4.

coin-change-problem

Coin change problem : Line of thought

As always, let’s start with brute force solution. We have two choices for a coin : Either we can include the coin in solution, or we can not include it in solution. If coin m is included in solution, problem reduces to find change for value N-V(m) using K coins. Notice that we can again use all the coins for reduced problem too.
If coin is not included in solution when value to changed is less than the denomination of coin. At this time, there is reduction in value to be changed, but we lose one coin, hence problem stands : Change value V with N-1 coins.
If we look at it, it is simple recursive formulation.

C(N,m) = C(N,m-1) + C(N- V(m), m)

coin change problem

When do we stop then? When do we know that there is no more solution going forward. If change is required for value zero, there is only one solution possible, which is to include no coin.

C(N,m) = 1 if N == 0

Also, what is solution if we do not have any coins with us at all and there is value to be changed. There is no solution then.

C(N,m) =0 if N > 0 and m < 0

Also, if value required is less than zero, then there is again no solution, given that all coins have positive values.

C(N,m) = 0 if N < 0

We see that problem reduces to smaller problems and then there are point when we can stop going forward. That’s a perfect condition for recursive solution.

Coin change problem : recursive implementation

package com.company;

/**
 * Created by sangar on 5.5.18.
 */
public class CoinChange {

    public static int coinChange(int value, int[] coins, int consideredCoin){
        /* If value to be changed is negative, since coins are positives,
        there is no way to change them
         */
        if(value < 0) return 0;

        /*When there may or may not be coins, and no value is
        required, there is one solution which is not to include any
        coin */
        if(value == 0) return 1;

        /* When there is value required by no coins left,
           there is not solution
         */
        if(value > 0 && consideredCoin == coins.length) return 0;
                // When coin is included
        return coinChange(value-coins[consideredCoin],coins, consideredCoin)
               //When coin is not included
            + coinChange(value,coins, consideredCoin + 1);
    }

    public  static void main(String[] args){
        int value = 4;
        int[] coins = {1,2,3};

        int count = coinChange(value, coins, 0);
        System.out.println(count);
    }
}

Complexity of recursive implementation of coin change solution is exponential O(2m) where m is number of coins.
For every coin we have 2 options, either we include it or exclude it so if we think in terms of binary, its 0(exclude) or 1(include). so for example if we have 2 coins, options will be [ 00, 01, 10, 11 ]. so its 22. For m coins , it will be 2m. In all these options we will be checking whether that selection has made the change which is required
Reason for this exponential complexity is that we are calculating smaller subproblems again and again.

coin change problem recursive tree

In discussion so far, we see two properties of the solution : First, there is optimal substructure, that is optimal solution to subproblems provides optimal solution to bigger problems. This is known as optimal substructure property. Second, subproblems are overlapping. These two condition as necessary for applying dynamic programming approach.
To avoid calculating same subproblem again and again, that we can avoid using simple memoization. Let’s create a two dimensional table Coins. Coins(i, j) represents the number of ways in which change for i can be made using j coins.
Now if jth coin is included, then numbers of ways will be Coins(i- v[j], j-1)
If jth coin is not included, number of ways will be  Coins (i, j-1). Adding both of them will give us

Coins(i,j) = Coins(i-v[j]) + Coins(i, j-1).

For all i = 0 Cost(i,j) = 1, for all j = 0 Cost(i,j) will 1 for all i > 0.
We can start bottom up and fill the table as per the formula above. Once we have filled the entire table, Coins(N,m) will be answer to the problem.

package com.company;

/**
 * Created by sangar on 5.5.18.
 */
public class CoinChange {

    public static int coinChangeDP(int value, int[] coins){

        int[][] numWays = new int[value+1][coins.length+1];

        for(int i = 0; i <= coins.length; i++ ){
            numWays[0][i] = 1;
        }

        for(int i = 1; i <= value; i++ ){
            numWays[i][0] = 0;
        }

        for(int i = 1; i <= value; i++){
            for(int j = 1; j <= coins.length; j++){
                numWays[i][j] = (i -coins[j-1] >= 0 ? numWays[i-coins[j-1]][j] : 0 )
                                 + numWays[i][j-1];
            }
        }

        return numWays[value][coins.length];
    }

    public  static void main(String[] args){
        int value = 4;
        int[] coins = {1,2,3};

        int count = coinChangeDP(value, coins);

        System.out.println(count);
    }
}

Example : for Value = 4 and coins {1,2,3}, below is the bottom up filling of table.

Complexity of dynamic programming implementation of coin change problem is O(Nm) where N is value and m is number of coins. Additional O(Nm) space is also required for memoization.

Please share if there is something missing or wrong. If you want to share your knowledge with thousands of learners across the world, please reach out to us on communications@algorithmsandme.com