# 10.39

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## A Python Solution - O(1)

```import sys
n = int(sys.argv)

OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s"
COINS = tuple(sorted((3, 4, 9, 20, 22, 23), reverse=True))
FAILSAFE_MAX = 9999999999

if len(COINS) < 1: raise Exception("Coins please!")
if len(COINS) == 1:
c = COINS
if n % c == 0:
print OUT_TMP % (n, n/c, [c]*(n/c))
sys.exit()
else:
raise Exception("Impossible!")

CAL_MAX = min(COINS * COINS, n+1)

min_coins_n = 
min_coins_l = [()]

for i in xrange(1, CAL_MAX):
if i in COINS:
min_coins_n.append(1)
min_coins_l.append((i,))
else:
current_min = -1
for c in COINS:
smaller_i = i - c
if smaller_i > 0 and min_coins_n[smaller_i] < FAILSAFE_MAX and \
(current_min == -1 or min_coins_n[smaller_i] < min_coins_n[current_min]):
current_min = smaller_i

if current_min != -1:
min_coins_n.append(min_coins_n[current_min] + 1)
l = list(min_coins_l[current_min]) # copy
l.append(i - current_min)
# another copy, not required but robuster code
ll = tuple(l)
min_coins_l.append(tuple(l))
else:
# not changable using the current coins
min_coins_n.append(FAILSAFE_MAX)
min_coins_l.append(None)

big_part_n = 0
coins_list = []
remaining_n = n
if n > CAL_MAX:
n_big_part = n - CAL_MAX
big_part_n = (n_big_part / COINS) + 1
coins_list = [COINS] * big_part_n
remaining_n -= big_part_n * COINS

final_n = big_part_n + min_coins_n[remaining_n]
if final_n >= FAILSAFE_MAX:
raise Exception("Impossible!")
coins_list.extend(min_coins_l[remaining_n])
print OUT_TMP % (n, final_n, coins_list)
```

## A Java solution - O(n)

```
public class CoinProblem {

public static void main(String[] args) {
int sumToMakeChangeFor = 20;
int[] coinDenominations = new int[]{1, 2, 5, 10};

System.out.println("Number of coins needed = " + numberOfCoinsNeededForChange(sumToMakeChangeFor, coinDenominations));
}

private static int numberOfCoinsNeededForChange(int sum, int[] coinDenominations) {
int[] minimumNumberOfCoinsNeeded = new int[sum + 1];
for (int i = 0; i <= sum; i++){
minimumNumberOfCoinsNeeded[i] = Integer.MAX_VALUE;
}
minimumNumberOfCoinsNeeded = 0;

for (int currentSum = 1; currentSum <= sum; currentSum++) {
for (int j = 0; j < coinDenominations.length; j++) {
if (coinDenominations[j] <= currentSum &&
((minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1) < minimumNumberOfCoinsNeeded[currentSum]))
minimumNumberOfCoinsNeeded[currentSum] = minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1;
}
}
return minimumNumberOfCoinsNeeded[sum];
}
}

```

Reference: Dynamic Programming, TopCoder.com

Back to Chapter 10