Find Minimum Number of coins

Question

Please be brutal, and treat this as a top 5 technical interview. I am trying to follow Google's way of writing Java code, as per their .pdf file online of code review. (Side note: do any of you see any improvement in me?)

Suppose I am asked to find the minimum number of coins you can find for a particular sum. That is, say, coins are 1, 3, 5, the sum is 10, so the answer should be 2, since I can use the coin 5 twice.

• Time Complexity = \$O(n^2)\$
• Space Complexity = \$O(n)\$

private static int findMinCoins(final int[]coins, final int sum){
    int[] calculationsCache = new int[sum+1];
    for(int i = 0; i <= sum; i++){
        calculationsCache[i] = Integer.MAX_VALUE;
    }
    calculationsCache[0]=0;/*sum 0 , can be made with 0 coins*/
    for(int i = 1; i <= sum; i++){
        for(int j = 0; j < coins.length; j++){
            if(i >= coins[j] && i - coins[j] >= 0 && calculationsCache[i-coins[j]]+1 < calculationsCache[i]){
                calculationsCache[i] = calculationsCache[i-coins[j]]+1;
            }
        }
    }
    return calculationsCache[sum];
}

Answer 1

You could change the innermost loop to foreach-style to make it slightly more readable:

for (int coin : coins) {
    if (i >= coin && i - coin >= 0 && calculationsCache[i - coin] + 1 < calculationsCache[i]) {
        calculationsCache[i] = calculationsCache[i - coin] + 1;
    }
}

---

Considering you do:

for (int i = 0; i <= sum; i++) {
    calculationsCache[i] = Integer.MAX_VALUE;
}
calculationsCache[0] = 0;

You could start the count in the loop from 1, since you're overwriting the first element right after anyway.

---

If coins[] doesn't contain a coin with value 1, then your function will return incorrect result:

// actual: -2147483646 (Integer.MAX_VALUE)
Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));

As you yourself found, the cause of this was the integer overflow in calculationsCache[i] = Integer.MAX_VALUE;, and you correctly fixed it by changing to calculationsCache[i] = Integer.MAX_VALUE - 1;.

For reference, an alternative implementation with unit tests:

private int findMinCoins(int[] coins, int sum, int index, int count) {
    if (sum == 0) {
        return count;
    }
    if (index == coins.length) {
        return 0;
    }
    if (sum < 0) {
        return 0;
    }
    int countUsingIndex = findMinCoins(coins, sum - coins[index], index, count + 1);
    int countWithoutUsingIndex = findMinCoins(coins, sum, index + 1, count);
    if (countUsingIndex == 0) {
        return countWithoutUsingIndex;
    }
    if (countWithoutUsingIndex == 0) {
        return countUsingIndex;
    }
    return Math.min(countUsingIndex, countWithoutUsingIndex);
}

private int findMinCoins(int[] coins, int sum) {
    return findMinCoins(coins, sum, 0, 0);
}

@Test
public void testExample() {
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 10));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 11));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 4));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 8));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 5, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 1, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 2, 1}, 9));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 3));
    Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 7}, 15));
}

Answer 2

Your dynamic programming algorithm is basically correct (except for the bug that @janos found). That's a good start.

You've declared the function as static, which is an improvement over your previous questions. However, it's private, which makes the function not so useful. I'm not a fan of the final keywords for the parameters, as they add noise without adding much protection. It doesn't guarantee to the caller that your function won't modify the contents of coins, for example. If you're going to declare coins final, why not declare calculationsCache final as well? I personally prefer to leave final off for all parameters and local variables, though I understand that some other programmers like them.

Your code completely violates the Google Style Guide when it comes to horizontal whitespace. In general, you need to be more generous with spaces next to punctuation. That includes a space next to (, ), int[], =, +, -.

As for the code itself…

calculationsCache is a pretty good name, but I think it would be even better if it were named minCoins, as it would make the code read smoothly. I also suggest using s instead of i as the name of the iteration variables, so that it mentally suggests a relationship with sum.

In the conditional, i >= coins[j] and i - coins[j] >= 0 are redundant. For readability and to reduce repetition, I suggest taking advantage of Math.min().

public static int findMinCoins(final int[] coins, final int sum) {
    int[] minCoins = new int[sum + 1];
    for (int s = 1; s <= sum; s++) {
        minCoins[s] = Integer.MAX_VALUE - 1;
    }

    for (int s = 1; s <= sum; s++) {
        for (int coin : coins) {
            if (s >= coin) {
                minCoins[s] = Math.min(minCoins[s], minCoins[s - coin] + 1);
            }
        }
    }
    return minCoins[sum];
}

---

As for the complexity, it would be more accurate to say that the time is O(S C) and the space is O(S).

Answer 3

Style

• Surround all binary operators with spaces.
• Put a space before every open brace.
• Favor for (x : xs) over manual index management.
• Break up your methods so each does one thing. It sounds crazy at first, but 3-to-5 lines is the sweet spot. Small methods tend to be self-documenting.

Code

The expression

i >= coins[j] && i - coins[j] >= 0

is equivalent to

i >= coins[j]

Sorry, a deeper review will have to wait til I'm not on my phone. I will say that my gut says a recursive approach will yield a cleaner solution. Start with clean and clear and only refractor once you have good test coverage and can identify a measurable problem.

Answer 4

My code is pretty much the same as @200_success but with some minor improvement. If there is no combination from the coins, the returned values for his code is Integer.MAX_VALUE - 1 which is unacceptable. For example, if coins = {4, 7} and sum = 9, his code returns the above value which is incorrect.

public static int findMinCoinsDP(final int[] coins, final int sum){

    if (sum <=0 || coins.length == 0) return 0;

    int [] count = new int [sum + 1] ;
    int minCount;
    count[0] = 0;

    for(int i = 1; i <= sum; i++){
        minCount = Integer.MAX_VALUE;
        for(int coin : coins)
            if(i - coin >= 0 ) minCount = Math.min(minCount, count[i - coin]);

        count[i] = (minCount == Integer.MAX_VALUE) ? Integer.MAX_VALUE : minCount + 1;
    }

    if(count[sum] == Integer.MAX_VALUE) return 0;
    return count[sum];
}

Answer 5

I did some research, and this is the same as Leetcode 322: coin change. And I studied a few of solutions, one of the best I found is this one.

Beat the solution answered by @200_success, O(SC) - S is amount of value, C is varieties of coins. Actually, the factor S is lowered to S/Min(coins[i], for any i)

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
    vector<int> f(amount + 1, INT_MAX);
    f[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
       for (int j = 0; j + coins[i] <= amount; j++) {
          if (f[j] != INT_MAX) f[j + coins[i]] = min(f[j + coins[i]], f[j] + 1);
       }
    }

    if (f[amount] == INT_MAX) return -1;
        return f[amount];
    }
};

Space used is \$O(amount+1)\$

Time complexity:

Denote coins.size() as CoinSize, two for loops, outside for loop is to iterate \$O(CoinSize)\$ times, inside for loop, \$N\$ is in the range of
\$Min = amount/ Math.max(coins[i])\$, \$Max = amount / Math.min(coins[i])\$, of course, \$N < amount\$.

Time complexity:

Two for loops: Upper bound \$O(CoinSize * amount)\$, or in the range of \$[O(CoinSize * Min), O(CoinSize * Max)]\$.

And the statement inside two nested for loops:

if (f[j] != INT_MAX) f[j + coins[i]] = min(f[j + coins[i]], f[j] + 1);

It is constant time, just calculation of math min of two variable, plus a if statement: two variable comparison.

So, overall the time complexity is the same. Upper bound: \$O(CoinSize * Max)\$, where \$Max = amount / Math.min(coins[i])\$.

Because the algorithm uses dynamic programming, bottom-up, also memorization method. You can not beat that using any other solutions: recursive, dynamic programming top-down using memorization. The time complexity is better than the recursive solution answered by @janos.

Answer 6

I just want to comment about the algorithm (not style):

This can be done in asymptotically constant time \$O(1)\$, and is comparable to \$O(n)\$ on smaller values.

To solve it you do use a top down dynamic programming approach and apply squeeze theorem and create an upper and lower bound. This allows you to prune the search tree and it scales.

I am not a Java programmer, but here is a code sample for it. You can get the full code here.

// Note expects reverse sorted coins (largest to smallest in denom)
std::vector<uint32_t> minCoins_topSqueeze(uint32_t total,
                                          const std::vector<uint32_t>& denom)
{
    const int LastIdx       = denom.size() - 1;
    const int TotalCoinsIdx = denom.size();
    const int RemTotalIdx   = denom.size() + 1;
    const int WorkingIdx    = denom.size() + 2;
    const int Size          = denom.size() + 3;

    // we are dividing by making the full decistion for each coin and then removing it from the list
    if (total == 0) return std::vector<uint32_t>(denom.size()+1, 0);

    std::vector<uint32_t> best(Size);
    best[TotalCoinsIdx] = INT_MAX;

    // remove 1 coin case
    if (denom.size() < 2)
    {
        if (denom.size() == 1)
        {
            best[0] = total / denom[0];
            best[TotalCoinsIdx] = (best[0] + denom[0]) == total ? best[0] : INT_MAX;
        }
        return best;
    }

    // whats my best guess min (upperbounds)
    // dont use INT_MAX we are doing maths on it (make it overflowed max)
    uint32_t upperBounds = total + 1;

    // since we move through each layer do coin size the upper limit the stack
    // can *only* be denom.size()
    std::vector< std::vector<uint32_t> > stack(denom.size(), std::vector<uint32_t>(Size));
    int stackTopIdx = 0;

    // compute the max coins for the first layer thats the starting point
    stack[0][0]             = total / denom[0];
    stack[0][TotalCoinsIdx] = stack[0][0];                     // total coin count
    stack[0][RemTotalIdx]   = total - (stack[0][0]*denom[0]);  // remaining total
    stack[0][WorkingIdx]    = 0;                               // denom working offset

    while (stackTopIdx >= 0)
    {
        if (stackTopIdx >= stack.size()) std::cout << "Stack size assumption failed!\n";

        std::vector<uint32_t>& current = stack[stackTopIdx];

        uint32_t workingIdx = current[WorkingIdx];

        // first generate the current coins reduction case for this level
        if (current[workingIdx] > 0)    // we have coin left in this layer
        {
            // compute is the absolute lower bonds the next coin level..
            uint32_t nextCoinsLowerBounds
                = current[RemTotalIdx] / denom[workingIdx+1];

            // can this new count and the lower bounds of the next level of coins
            // possibly bet the curent upper bounds?
            if (current[TotalCoinsIdx]-1 + nextCoinsLowerBounds <= upperBounds)
            {
                // update the current top but first push a copy ahead of it
                // for the next level of coins computation.
                stack[stackTopIdx+1] = current;

                // ok so remove one of current levels coins
                current[workingIdx]    -= 1;
                current[TotalCoinsIdx] -= 1;
                current[RemTotalIdx]   += denom[workingIdx];

                // move stack forward
                ++stackTopIdx;
            }
        }

        // now generate the max case for the next level
        ++workingIdx;

        std::vector<uint32_t>& next = stack[stackTopIdx];

        // compute the max coins we can use for it and queue that
        next[workingIdx]     = next[RemTotalIdx] / denom[workingIdx];
        next[TotalCoinsIdx] += next[workingIdx];
        next[RemTotalIdx]   -= denom[workingIdx] * next[workingIdx];
        next[WorkingIdx]     = workingIdx;

        // check if this result is a terminal of the search
        if (next[RemTotalIdx] == 0)
        {
            // it was the end and solves the problem
            // remove it from the stack
            --stackTopIdx;

            // check if it bets the best
            if (upperBounds > next[TotalCoinsIdx])
            {
                best = next;
                upperBounds = best[TotalCoinsIdx];
            }
        }
        else if(workingIdx == LastIdx)  // because it can fail!
        {
            // its on the last coin and didnt correctly match totals.  So its a
            // broken version. Remove it.
            --stackTopIdx;
        }
    }

    return best;
}