Modified Coin Change
November 19, 2019
This is a trick question.
In the general coin change problem, dynamic programming is required because the greedy algorithm doesn’t work for some sets of coins. But with the coins restricted to powers of 5, the greedy algorithm does work. And, in fact, there is an even simpler algorithm; express the number in base 5 and sum its digits:
(define (f n) (sum (digits n 5)))
> (f 42) 6 > (f 142) 6
That’s 25+5+5+5+1+1 for the first problem, and 125+5+5+5+1+1 for the second problem. You can run the program at https://ideone.com/bgOJvY.
Here’s a solution in Python.
Output:
Here’s a solution in C that’s similar to the Python solution I posted earlier.
Example Usage: