Modified Coin Change Problem with Infinite Coins of Denominations of Powers of 5

2
votes

We are given a set of denominations and a total amount.

  • Infinite coins of each denomination are available
  • All denominations are powers of 5

We have to find the minimum number of coins needed to make the total.

I wish to know the logic behind the solution. Thanks in advance.

1
algorithmdynamic-programmingcoin-change
This is just the sum of the total’s digits, base 5. – RBarryYoung

1 Answers

0
votes

If we denote the denominations as [w1, w2 ... wn], such that wi = 5 × wi+1, then the denominations forms a superincreasing sequence. The page lists a general greedy algorithm if the denominations are powers of K, where K ≥ 2.

The proof is simple, if you remove a single coin of denomination wi, you would need at least 5 coins of lower denomination to get the same sum.