Fewest Coins When Change Is Given
You pay a price with coins of 1, 5, 10, 50, 100 and 200, and the cashier gives change in the same coins. You may overpay. Return the fewest coins that change hands in total — the coins you pay plus the coins you get back.
fewestCoinsWithChange(95) -> 2 // pay 100, get 5 back fewestCoinsWithChange(7) -> 3 // pay 5 + 1 + 1 fewestCoinsWithChange(0) -> 0
Hints
Hint 1
coins(x), the fewest coins making exactly x, is the classic coin-change DP (or greedy, since these denominations are canonical).
Hint 2
Try every payment P from the price up to the price plus 199: the total is coins(P) + coins(P − price). Change of 200 or more is never optimal, because both sides could drop a 200 coin.