2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What specifically confuses you about returning -1 to stop the recursion? \$\endgroup\$ – πάντα ῥεῖ Apr 16 '18 at 20:04
  • \$\begingroup\$ There are three conditions 1) when amount is more than current coin (2) when amount is less than current coin and (3) when amount is same as current coin. How to easily keep track of all these three conditions in recursion? The confusing part is I have to apply conditionals at two places to check for -1. \$\endgroup\$ – CodeYogi Apr 16 '18 at 20:08
  • \$\begingroup\$ And btw why this is down voted? \$\endgroup\$ – CodeYogi Apr 16 '18 at 20:08
  • \$\begingroup\$ You might want to add that clarification to your question instead of burying it into the comments. \$\endgroup\$ – πάντα ῥεῖ Apr 16 '18 at 20:33
  • \$\begingroup\$ Yes, adding that would help, but I wouldn't include the question part when you add it. Instead maybe an explanation of why you did it your way. \$\endgroup\$ – Raystafarian Apr 16 '18 at 21:29
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately this relies on the assumption that each number smaller than amount is also solvable. Fails on 2, 5, 10 and 27, as 1 does not have a solution. \$\endgroup\$ – mtj Apr 17 '18 at 9:05
  • \$\begingroup\$ Good catch! The problem was an integer overflow that I had not accounted for, I have updated the code and added support for cases where coins isn't a sorted array. \$\endgroup\$ – maxb Apr 17 '18 at 9:19
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.