Coin Change (Greedy)

Given coin denominations and a target amount, make change using the fewest coins. The greedy approach repeatedly takes the largest coin not exceeding the remainder. This works for canonical systems like US coins but fails for arbitrary denominations — then you need DP. This lesson covers the greedy algorithm, when it is optimal, counterexamples, and implementations in C, Java, and Python with trace tables.

Overview

A cashier making change naturally picks the biggest coin first. That instinct is a greedy algorithm — fast and correct for many real currency systems, but not universally optimal.

US coins [25, 10, 5, 1] — amount 30:
  Take 25 → remainder 5
  Take 5  → remainder 0
  Answer: 2 coins ✓

Arbitrary coins [1, 3, 4] — amount 6:
  Greedy: 4 + 1 + 1 = 3 coins
  Optimal: 3 + 3 = 2 coins → greedy fails, use DP

Problem Statement

Input: Coin denominations coins[] (unlimited supply of each) and target amount amount.

Output: Minimum number of coins to sum exactly to amount, or indicate impossibility if no combination exists.

Greedy sub-problem: At each step, use as many of the largest coin ≤ remaining amount as possible.

Complexity (greedy): O(n) per amount if coins are pre-sorted, where n = number of denominations; O(n log n) if sorting first.

Greedy Algorithm

1. Sort coins in decreasing order.
2. Set remaining = amount and count = 0.
3. For each coin c:
   • Take k = remaining // c coins of value c.
   • Add k to count; subtract k × c from remaining.
4. If remaining == 0, return count; else no exact change (or greedy incomplete for non-canonical systems).

When Greedy Works

A coin system is canonical if the greedy algorithm produces the minimum number of coins for every amount.

• US coins {1, 5, 10, 25} — canonical (greedy optimal).
• Euro coins {1, 2, 5, 10, 20, 50, 100, 200} cents — canonical.
• Binary / powers of two {1, 2, 4, 8, …} — greedy equals optimal.

Sufficient (not necessary) condition: if each coin is at least the sum of all smaller coins, greedy works. US coins satisfy a looser structural property that still guarantees optimality.

When Greedy Fails

Code (C, Java, Python)

Python

def coin_change_greedy(coins, amount):
    """Min coins via largest-first greedy. Optimal only if system is canonical."""
    coins = sorted(coins, reverse=True)
    count = 0
    remaining = amount
    used = []

    for coin in coins:
        if remaining <= 0:
            break
        k = remaining // coin
        if k:
            count += k
            remaining -= k * coin
            used.extend([coin] * k)

    if remaining != 0:
        return -1, []  # exact change impossible with these coins
    return count, used


if __name__ == "__main__":
    c, used = coin_change_greedy([25, 10, 5, 1], 41)
    print(f"count = {c}, coins = {used}")  # 4, [25, 10, 5, 1]

Java

import java.util.Arrays;

public class CoinChangeGreedy {

    /** Largest coin first — correct for canonical systems like US coins. */
    public static int minCoinsGreedy(int[] coins, int amount) {
        Integer[] sorted = Arrays.stream(coins).boxed().toArray(Integer[]::new);
        Arrays.sort(sorted, (a, b) -> b - a);

        int count = 0, remaining = amount;
        for (int coin : sorted) {
            if (remaining <= 0) break;
            int k = remaining / coin;
            count += k;
            remaining -= k * coin;
        }
        return remaining == 0 ? count : -1;
    }

    public static void main(String[] args) {
        int[] us = {25, 10, 5, 1};
        System.out.println(minCoinsGreedy(us, 41)); // 4
        System.out.println(minCoinsGreedy(new int[]{1, 3, 4}, 6)); // 3 (not optimal)
    }
}

C

#include <stdio.h>
#include <stdlib.h>

int cmp_desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int coin_change_greedy(int coins[], int n, int amount) {
    qsort(coins, n, sizeof(int), cmp_desc);
    int count = 0, i, remaining = amount;

    for (i = 0; i < n && remaining > 0; i++) {
        int k = remaining / coins[i];
        count += k;
        remaining -= k * coins[i];
    }
    return remaining == 0 ? count : -1;
}

int main(void) {
    int us[] = {25, 10, 5, 1};
    printf("%d\n", coin_change_greedy(us, 4, 41)); /* 4 */
    int bad[] = {1, 3, 4};
    printf("%d\n", coin_change_greedy(bad, 3, 6));  /* 3 — greedy, not optimal */
    return 0;
}

Output & Trace

US coins — amount 41, denominations [25, 10, 5, 1]

Coins used: 25 + 10 + 5 + 1 = 41 with 4 coins (optimal for US system).

More examples

Greedy vs DP (LeetCode 322)

LeetCode 322 — Coin Change asks for minimum coins with arbitrary denominations. Use DP, not greedy:

def coin_change_dp(coins, amount):
    """LeetCode 322 — min coins for any denomination set. O(n * amount)."""
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

# coins=[1,3,4], amount=6 → 2 (not greedy's 3)

Rule of thumb: US/Euro-style currency → greedy is fine. Unknown or custom coins → DP.

Variants & Related Problems

Approach Comparison

Real-Life Applications

Interview Tips

1. Ask: are denominations standard/canonical or arbitrary?
2. State greedy: sort descending, take max coins of each denomination.
3. Give counterexample coins=[1,3,4], amount=6 immediately when discussing failure.
4. For LeetCode 322, write 1D DP: dp[a] = min(dp[a], dp[a-coin]+1).
5. Mention unlimited vs bounded coin counts — changes the DP state.
6. Link back to greedy introduction and DP introduction for the full picture.