Coin Change Problem

Problem Statement

We are given an array of coins having different denominations and an integer sum representing the total money, you have to return the fewest coins that you will need to make up that sum if it’s not possible to construct that sum then return -1.

Example : 

Input: [1,2,3,4,5]
Sum: 16
Output: 4
Explanation: Four coins require to make the desired sum [5,5,5,1]

Input: [1,2,5,9,8]
Sum: 17
Output: 2
Explanation: Two coins require to make the desired sum [9,8]

Input:  [2, 4, 6, 8]
Sum: 15
Output: -1
Explanation: There is no combination present with sum 15.

Simple Approach

The naive approach is to check for every combination of coins for the given sum.

In this approach, we can use recursion to solve this as we have to iterate over all the possible combinations of coins that equal the given sum every time update the minimum no of coins needed to create this sum.

C++ Code

int coinChange(vector<int> const &S, int sum)
{
    if (sum == 0) {
        return 0;
    }
    if (sum < 0) {
        return INT_MAX;
    }
    int coins = INT_MAX;
    for (int i: S)
    {
        int result = coinChange(S, sum - i);
        if (result != INT_MAX) {
            coins = min(coins, result + 1);
        }
    }
    return coins;
}

Java Code

public static int coinChange(int[] S, int sum)
    {
        if (sum == 0) {
            return 0;
        }
        if (sum < 0) {
            return Integer.MAX_VALUE;
        }
        int coins = Integer.MAX_VALUE;
        for (int c: S)
        {
            int result = coinChange(S, sum - c);

            if (result != Integer.MAX_VALUE) {
                coins = Integer.min(coins, result + 1);
            }
        }
        return coins;
    }

Python Code

def coinChange(S, sum):

    if sum == 0:
        return 0

    if sum < 0:
        return sys.maxsize

    coins = sys.maxsize

    for c in S:

        result = coinChange(S, sum - c)

        if result != sys.maxsize:
            coins = min(coins, result + 1)

    return coins

Time complexity: Exponential. (every recursive call is making n recursive calls)
Space complexity: O(1)

Efficient Approach: Dynamic Programming

As the problem can be broken down into smaller subproblems as there are many overlapping subproblems in the recursive tree and we will avoid solving them again and again.

We are using a bottom-up approach i.e we solve the small problem first then move to larger subproblems from the smaller ones as we will compute dp[i] 1<=i<=subproblems storing the ans as minimum coins needed to create the sum.

• Defining subproblems: CoinChange needed for any x values smaller than n, # subproblems O(n)
  DP(x)
• Make a guess that would take us one step closer to the solution:
  which coin to take
• Recurrence or relate the subproblems together:
  DP(x) = min([DP(x-c) for c in coins]) + 1 # time per subproblem O(len(coins))
• Think about the topological orders for bottom up implementation:
  We want to know the value with smaller x first, so the for loop starts from 0.
  The initial state DP(0) = 0, take 0 coin for amount 0
• Define the original problem/think whether the DP can solve the original problem:
  DP(n) Also remember to think of implementation details/corner cases at this step, for instance, how to deal with x-c<0 in steps 3.

C++ Implementation

int coinChange(vector<int> const &arr, int sum)
{
    int dp[sum + 1];
    for (int i = 1; i <= sum; i++)
    {
        dp[i] = INT_MAX;
        int result = INT_MAX;

        for (int c: arr)
        {
            if (i - c >= 0) {
                result = dp[i - c];
            }

            if (result != INT_MAX) {
                dp[i] = min(dp[i], result + 1);
            }
        }
    }

    return dp[sum];
}

Java Implementation

public static int coinChange(int[] S, int sum)
    {
        int[] dp = new int[sum + 1];

        for (int i = 1; i <= sum; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            int result = Integer.MAX_VALUE;

            for (int c: S)
            {
                if (i - c >= 0) {
                    result = dp[i - c];
                }

                if (result != Integer.MAX_VALUE) {
                    dp[i] = Integer.min(dp[i], result + 1);
                }
            }
        }

        return dp[sum];
    }

Python Implementation

def coinChange(S, sum):

    dp = [0] * (sum + 1)

    for i in range(1, sum + 1):

        dp[i] = sys.maxsize

        for c in range(len(S)):
            if i - S[c] >= 0:
                result = dp[i - S[c]]

                if result != sys.maxsize:
                    dp[i] = min(dp[i], result + 1)

    return dp[sum]

Time complexity: O(n*sum)  n- no of distinct coins, sum- desired sum.
Space complexity: O(sum)

Practice Question

Coin Sum Infinite
Dynamic Programming

FAQs

How do you solve a coin change problem?
We solve the coin change problem using dynamic programming

What is the time complexity of the coin change problem?
The time complexity of the coin change problem is O(n*sum) n is the no of distinct coins and sum is the target sum we have to create.

Is coin change greedy?
No, it can’t be solved using the greedy approach.