Minimum Notes for a Given Amount

Minimum Notes for a Given Amount is the classic cashier problem. Given the bills in your drawer, hand the customer their change using as few notes as possible. It is the cleanest introduction to a greedy strategy: at every step, grab the biggest thing that still fits.

The slow way first

You could search every combination of notes that sums to the amount and keep the smallest — that is a full coin-change search, and it explores an exponential number of possibilities. For making change with a normal currency system, that is wildly more work than needed.

The question to ask: do I ever regret taking the largest note that fits? For a canonical currency (each denomination is a clean multiple-friendly step up from the last), the answer is no. Taking the biggest note can only shrink the remaining amount faster, and no clever combination of smaller notes beats it.

The idea: biggest note first, every time

Sort the denominations from largest to smallest. Walk them in that order. For the current note, take as many as fit — that is just amount // note of them — add that to your count, and subtract their value from the amount. Move to the next, smaller note and repeat until the amount reaches zero.

The key insight: because the notes are sorted descending, the first note big enough to fit is always the best one to use, so a single left-to-right pass is enough — no backtracking.

Walk through it

Step through the animation. The pointer scans denominations biggest first. 100 is too big for 93, so we skip it. 50 fits once (43 left), 20 fits twice (3 left), 10 and 5 are too big, and 1 fits three times — bringing the remaining amount to 0 with a total of 6 notes.

Pseudocode

sort notes from largest to smallest
count = 0
for each note in notes:
    take = amount // note          # how many of this note fit
    count = count + take
    amount = amount - take * note  # remove their value
return count

The Python solution

def min_notes(amount, notes):
    notes = sorted(notes, reverse=True)
    count = 0
    for note in notes:
        take = amount // note
        count += take
        amount -= take * note
    return count

• We sort the denominations descending so the loop always sees the biggest usable note first.
• take = amount // note is integer division — how many whole notes of this value fit into what is left.
• count += take records the notes handed out for this denomination.
• amount -= take * note removes exactly the value we just dispensed, leaving the remainder for smaller notes.
• When the loop ends the amount is 0, and count is the minimum number of notes.

Complexity

The sort dominates at O(n log n); the single pass over the n denominations is O(n). Apart from the sorted list we use only a couple of counters, so the extra space is O(1).

When this pattern shows up

Practice