Coins Handed Back
A vending machine gives change using coins worth 200, 100, 50, 20, 10, 5, 2 and 1 cents, with an unlimited supply of each. It hands out coins one at a time, always the largest coin that does not exceed what is still owed, until nothing is owed. For these coin values that rule also uses the fewest coins possible.
Return the list of coin values handed out for cents, in the order they are handed out (largest first). Return an empty list when cents is 0.
Example 1
cents 388
returns [200,100,50,20,10,5,2,1]
388 = 200 + 100 + 50 + 20 + 10 + 5 + 2 + 1, one coin of each value.
Example 2
cents 9
returns [5,2,2]
9 = 5 + 2 + 2: after the 5, the largest coin that fits in 4 is a 2, twice.
Constraints
0 <= cents <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Coins on the TableBeginner
- Fewest BanknotesBeginner
- Fewest JugsBeginner
- Greedy CoinsBeginner
- Least Total Waiting TimeBeginner
- Most Tasks in a Time BudgetBeginner
- Only the Best CountBeginner
- Shortest Walk to SeatsBeginner