Minimum Coins (Canonical System)

Minimum Coins asks for the fewest coins that add up to a target amount. For a canonical coin system (like US coins), a simple greedy rule works perfectly: always grab the biggest coin that still fits.

The slow way first

The general version of this problem (arbitrary coin systems) needs dynamic programming — an O(amount × coins) table — because greedy can fail. For coins = [1, 3, 4] and amount = 6, greedy takes 4 + 1 + 1 = 3 coins, but the best is 3 + 3 = 2.

The question to ask: is this coin system canonical? For US-style currency (and many others), the denominations are chosen so the greedy choice is always part of an optimal answer. When that holds, we can skip the whole DP table and just walk the coins once.

The idea: biggest coin first, every time

Sort the coins from largest to smallest. Walk through them. For each coin, take as many copies as fit into the remaining amount, subtracting and counting each time. Because the system is canonical, the largest fitting coin is never a mistake — so we never need to reconsider.

The key insight: greedy works only because the system is canonical. The same code on a non-canonical system can overshoot the optimal count.

Walk through it

Step through the animation. The coin pointer moves left to right across the sorted denominations. remaining shrinks as we subtract, and count ticks up with each coin taken. We take one 25, one 10, one 5, and one 1, ending with remaining = 0 and count = 4.

Pseudocode

sort coins from largest to smallest
count = 0
for each coin:
    while coin fits in the remaining amount:
        subtract coin from amount
        count = count + 1
if amount is still greater than 0:
    return -1                 # cannot make exact change
return count

The Python solution

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while coin <= amount:
            amount -= coin
            count += 1
    if amount > 0:
        return -1
    return count

• coins.sort(reverse=True) puts the biggest denomination first so greedy can grab it.
• count tallies how many coins we have used so far.
• The for loop visits each denomination once, largest to smallest.
• The while coin <= amount loop takes as many copies of the current coin as fit, subtracting and counting each one.
• After the loop, if amount > 0 the target was unmakeable (e.g. no penny in the system), so we return -1.

Complexity

The sort is O(n log n) where n is the number of denominations (usually tiny). The subtraction loop runs once per coin taken. We use only a couple of counters, so O(1) extra space.

When this pattern shows up

Practice