Find the minimum number of coin change

Question

Description:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

coins = [1, 2, 5], amount = 11, return 3 (11 = 5 + 5 + 1)

coins = [2], amount = 3, return -1.

Code:

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount <  0) return -1;

        int min = -1;
        for (int coin : coins) {
            int currentMin = coinChange(coins, amount - coin);

            // if amount is less than coin value
            if (currentMin >= 0) {
                min = min < 0 ? currentMin : Math.min(currentMin, min);
            }
        }

        return min < 0 ? -1 : min + 1;
    }
}

Questions:

This question has slight deviation from normal one where we just need to return 0, returning -1 got me confused and I found it really hard to think in terms of recursion and handling edge cases.

PS: The solution works perfectly.

Answer 1

If you want to be good at interview questions, one thing you have to be able to spot is dynamic solutions. The algorithm you have proposed is correct, and does solve the problem, but the complexity is O(k^n) (I think it's a bit lower), where k is the number of coins you have, and n is the amount.

A dynamic solution can run in O(n*k), which is a lot faster even for small problem sizes. To make the solution dynamic, the way to go is usually to trade a bit of space for a lot of time. Here's my proposed solution:

public static int dynamicChange(int[] coins, int amount) {

    int[] changes = new int[amount+1];

    for (int i = 1; i <= amount; i++) {
        int minChange = Integer.MAX_VALUE/2;
        // loop over all coins which yield a non-negative remainder
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                if (changes[i-coins[j]] < minChange) {
                    minChange = changes[i-coins[j]];
                }
            }
        }
        changes[i] = minChange + 1;
    }
    return changes[amount] < Integer.MAX_VALUE/2 ? changes[amount] : -1;
}

It produces identical results, and is faster for any number of coins > 1. If the input only has a single coin, the trade-off of creating an array is too expensive. However, the problem becomes trivial when you only have one denomination.

Given the "standard" input of coins = [1, 2, 5], the dynamic solution is 10 times faster for amount = 11, and becomes 1000 times faster for amount >= 27.

EDIT: corrected code, and enabled handling of non-sorted denominations.

Answer 2

I think part of your problem is, you aren't taking the recursion far enough. I would suggest, that the loop be replaced by recursion. This can be accomplished quite easily by making sure the array is sorted first, and advancing from highest to lowest. Since this will require extra parameters and the addition of calling the sort function. Making the recursive function private and using a public helper overload, will neaten things quite a bit. Something like this should work:

public class Solution
{

    public static int coinChange(int[] coins, int amount)
    {
        Arrays.sort(coins);
        return coinChange(coins, amount, coins.length - 1, 0);
    }

    private static int coinChange(int[] coins, int amount, int index, int numCoins)
    {
        if (amount == 0)
        {
            return numCoins;
        }
        if (amount < coins[0])
        {
            return -1;
        }
        if (amount >= coins[index])
        {
            int tempCoins = (int) (amount / coins[index]);
            int tempAmount = amount - (tempCoins * coins[index]);
            if (tempAmount == 0 || tempAmount >= coins[0])
            {
                amount = tempAmount;
                numCoins += tempCoins;
            }
        }
        index--;

        return coinChange(coins, amount, index, numCoins);
    }
}

The usage would still be the same(int numCoins = Solution.coinChange(new int[]{1,2,5},11);).

Your description of the problem didn't mention whether the array would be sorted. If it is guaranteed to be sorted that line can be left out.

You'll notice that there are still 3 states to check for, but that each one is only checked for once per recursion.

I didn't like the idea of making the amount go below 0. Simply stopping when the amount was either 0 or less than the smallest coin, seems a cleaner way of doing things, to me.