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));
}
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 ofprivate
) \$\endgroup\$ – abuzittin gillifirca Apr 17 '14 at 6:24