Cash Register Change

Medium · rating 1200 · greedy, math

A cash register dispenses change using quarters (25¢), dimes (10¢), nickels (5¢) and pennies (1¢). Read an amount in cents. Print the minimum number of coins needed to make exactly that amount.

Constraints: 0 ≤ amount ≤ 10⁹

Editorial

Cash Register Change asks for the fewest coins to make an amount using U.S. denominations (25, 10, 5, 1) — a classic greedy problem.

Approach

Repeatedly take the largest coin that fits. For the U.S. (canonical) coin system this greedy choice is provably optimal.

count = 0
for coin in [25, 10, 5, 1]:
    count += amount // coin
    amount %= coin
return count

Important caveat

Greedy only works for canonical coin systems. For arbitrary denominations it can fail (e.g. coins 1, 3, 4 making 6), where you need the dynamic-programming approach from Coin Change.

Complexity

Time: O(coin types). Space: O(1).

Open Cash Register Change in Code Arena →