☕ DSA Java Articles

Topics › Greedy Algorithms › Easy Problems

Minimum coins

Hard TUF ID 319 SDE

Java source ↗ Edit this article ↗

Problem

You need to pay an amount V using Indian currency. You have an unlimited supply of coins and notes of the denominations {1, 2, 5, 10, 20, 50, 100, 500, 1000}. Find the minimum number of coins and notes that add up to exactly V, and return the denominations used, largest first. The count asked for in some versions is just the size of that list.

This is the greedy-algorithm version of the coin problem: the denominations are fixed and have a special structure that makes a simple greedy choice optimal. For arbitrary denominations the problem needs dynamic programming, and the article shows both so that you know when the shortcut is allowed.

Constraints: 0 ≤ V, and V fits in an int. The methods take the denominations as a sorted array, so the same code can be tried on other coin systems.

Example 1

V = 70
answer = [50, 20]          // 2 notes; no single note equals 70

Example 2

V = 121
answer = [100, 20, 1]      // 3 coins/notes

Approach 1: Dynamic programming, correct for any coin system

Intuition. Look at an optimal way to pay v and remove any one coin c from it. What is left pays v - c, and it must itself be optimal for v - c; otherwise we could swap in a better way to pay v - c and beat the “optimal” answer for v. So:

best[v] = 1 + min over coins c ≤ v of best[v - c], with best[0] = 0.

Filling best from 0 up to V gives the minimum count. To recover which coins were used, walk back from V: at amount v, any coin c with best[v - c] == best[v] - 1 lies on an optimal path. Trying coins from largest to smallest makes the reconstructed list come out largest first.

Algorithm.

  1. best[0] = 0; every other entry starts as “unreachable” (Integer.MAX_VALUE).
  2. For v = 1..V, for every coin c ≤ v with best[v - c] reachable, set best[v] = min(best[v], best[v - c] + 1).
  3. If best[V] is unreachable, return null.
  4. Starting at v = V, repeatedly pick the largest coin c with best[v - c] == best[v] - 1, record it, and subtract it, until v = 0.
static List<Integer> dynamicProgramming(int[] coins, int amount) {
    int[] best = new int[amount + 1];               // best[v] = fewest coins that make exactly v
    Arrays.fill(best, Integer.MAX_VALUE);
    best[0] = 0;
    for (int v = 1; v <= amount; v++) {
        for (int c : coins) {
            if (c <= v && best[v - c] != Integer.MAX_VALUE) best[v] = Math.min(best[v], best[v - c] + 1);
        }
    }
    if (best[amount] == Integer.MAX_VALUE) return null;    // amount cannot be formed at all
    List<Integer> used = new ArrayList<>();
    int v = amount;
    while (v > 0) {
        for (int i = coins.length - 1; i >= 0; i--) {      // largest coin that keeps us on an optimal path
            int c = coins[i];
            if (c <= v && best[v - c] == best[v] - 1) {
                used.add(c);
                v -= c;
                break;
            }
        }
    }
    return used;
}

Complexity. Time O(V × k) where k is the number of denominations (9 here). Space O(V) for the table.

This is always correct, but the table grows with V. For V = 10^9 it would need gigabytes of memory, even though the actual answer is about a million 1000-notes plus a handful of small coins. The greedy approach avoids the table entirely.

Approach 2: Optimal, greedy (largest denomination first)

Intuition. Pay as you would at a shop: hand over the largest note that does not exceed what you still owe, and repeat. For V = 121 that is 100, then 20, then 1.

Greedy is not correct for every coin system (see the pitfalls), so it is worth seeing why it is correct for this one. First, an optimal answer never contains certain combinations, because each can be replaced by fewer coins of the same total:

combination replace with
1 + 1 2
2 + 2 + 2 5 + 1
2 + 2 + 1 5
5 + 5 10
10 + 10 20
20 + 20 + 20 50 + 10
20 + 20 + 10 50
50 + 50 100
5 × 100 500
500 + 500 1000

With those combinations ruled out, the largest possible total of coins smaller than each denomination is always less than that denomination: below 2 at most 1; below 5 at most 2 + 2 = 4; below 10 at most 5 + 2 + 2 = 9; below 20 at most 10 + 9 = 19; below 50 at most 20 + 20 + 9 = 49; below 100 at most 50 + 49 = 99; below 500 at most 4 × 100 + 99 = 499; below 1000 at most 500 + 499 = 999.

Now let d be the largest denomination with d ≤ V. An optimal answer cannot use anything larger than d (it would exceed V), and the coins smaller than d add up to less than d ≤ V. So the optimal answer must contain d itself. That is exactly the greedy choice. Remove d, and the same argument applies to V - d. By induction, greedy produces an optimal answer for every V. The Java file also confirms this exhaustively for every V from 0 to 2000 by comparing greedy against the DP.

Algorithm.

  1. Walk the denominations from largest to smallest.
  2. While the remaining amount is at least the current denomination, take it and subtract it.
  3. Return the list of denominations taken.
static List<Integer> greedy(int[] coins, int amount) {
    List<Integer> used = new ArrayList<>();
    for (int i = coins.length - 1; i >= 0; i--) {  // coins are sorted ascending, so walk from the end
        while (amount >= coins[i]) {
            amount -= coins[i];
            used.add(coins[i]);
        }
    }
    return used;
}

Dry run on V = 121:

denomination remaining before taken remaining after
1000, 500 121 none 121
100 121 100 21
50 21 none 21
20 21 20 1
10, 5, 2 1 none 1
1 1 1 0

Result [100, 20, 1], three items.

Complexity. Time O(k + m) where m is the number of coins in the answer: each denomination is visited once and each loop iteration produces one coin. Space O(1) besides the output list. If only the count is needed, replace the inner loop by count += amount / c; amount %= c;, which is O(k) regardless of V.

Edge cases and pitfalls