# Find Minimum Number of coins

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];
}
• Can you provide the link to that pdf ? – konijn Apr 16 '14 at 22:05
• – bazang Apr 16 '14 at 22:28
• Please do not edit the question in a way that invalidates an answer. I've rolled back your question to Rev 4. You may post the correction as an answer to your own question instead. – 200_success Apr 17 '14 at 0:52
• findMinCoins(new int[]{2}, 1) == Integer.MAX_VALUE but correct answer is: "Can't be done." Also Are you given the method signature? (I think not on account of private) – abuzittin gillifirca Apr 17 '14 at 6:24
• You don't define what you mean by n. Your algorithm looks like it has runtime O(sum * coins.length) and space O(sum). – CodesInChaos Apr 17 '14 at 11:08

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));
}

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).

• I wholeheartedly agree about final. I use it only for fields and variables used in anonymous inner classes (I.e. where the compiler requires it). It can be exceedingly misleading on parameters, implying arrays and objects cannot be modified, which you rightly point out is not the case. – David Harkness Apr 17 '14 at 1:48
• @200_success to be honest, I never used final in actual code that I wrote. It was here, that someone yelled at me for not using final for variables, and I figured before I show up at my interview, perhaps it's a blunder on my part that I have to fix. – bazang Apr 18 '14 at 2:01

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.

• The problem with a recursive approach is that it can easily run out of stack. So it's a good idea to take a look at the sizes you need to support to see if a particular recursive approach causes a stackoverflow before actually implementing it. – CodesInChaos Apr 17 '14 at 11:18
• @David Harkness what do you mean by surround all binary operators with spaces? – bazang Apr 18 '14 at 1:56
• And if I am writing this at a Google interview, I'm sure the interviewer would probably not like a bunch of sub functions for something that could be done in 6-7 lines in general? Wouldn't that be an overkill? – bazang Apr 18 '14 at 1:57
• @bazang Put whitespace around operators for readability and because it matches Google's style guide,that's , x = y + 2 vs. x=y+2. In an interview, your process will be watched. If you demonstrate early how to decompose functions, that's one less thing the company will need to teach you. – David Harkness Apr 18 '14 at 2:21
• @bazang Keep in mind that the process is more about seeing your reaction and progression. This site is about reviewing working, real-world code. At least touch on these subjects in an interview, but be prepared to demonstrate that you can do it--not just speak to it. I won't care about 6 vs. 15 minutes. I will be inferring your abilities from the little code you write. Take your time and do it right! Ask questions. Be precise. Point out deficiencies you'd correct with more time and offer to do it right there. – David Harkness Apr 18 '14 at 2:21

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];
}

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.

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;
}