Skip to content

When Greedy Fails

The Most Important Lesson in This Chapter

Before you can master greedy algorithms, you must internalize when they fail.

A wrong greedy solution is worse than no solution. It gives you Wrong Answer with full confidence. You'll submit it, get WA, and spend an hour debugging — all because you didn't stop to ask "does this actually work?"

This lesson is about developing that instinct.

The Problem That Breaks Obvious Greedy

ABC099C — Strange Bank: You need to withdraw exactly N yen. The bank allows withdrawals in specific amounts:

  • 1 yen (always)
  • Powers of 6: 6, 36, 216, 1296, 7776, ...
  • Powers of 9: 9, 81, 729, 6561, ...

Each withdrawal is one operation. Minimize the number of operations.

The Greedy Choice: There isn't one — that's the point. Greedy fails here because denominations 6 and 9 interact in ways greedy can't see. Use DP.

Your first instinct: use the largest denomination that fits, repeat. This is the coin change greedy — it works for standard currency systems (1¢, 5¢, 10¢, 25¢).

Let's test it.

Watching Greedy Fail

Greedy vs optimal for N=48 with denominations {1, 6, 9, 36} — greedy uses 5 coins, optimal uses 3

For N = 48, the denominations available are: 1, 6, 9, 36.

Greedy (largest first): - 36 fits into 48. Take it. Remaining: 12. - 9 fits into 12. Take it. Remaining: 3. - 6 doesn't fit into 3. Skip. - 1. Take 3 of them. Remaining: 0. - Total: 1 + 1 + 3 = 5 operations.

But the optimal is: - 36 + 6 + 6 = 48. 3 operations.

The greedy got 5, the optimal is 3. Greedy is wrong here.

Let's trace the greedy and the optimal side by side:

Step Greedy choice Remaining Optimal choice Remaining
1 36 12 36 12
2 9 3 6 6
3 1 2 6 0 ✓
4 1 1 — —
5 1 0 ✓ — —

The greedy's mistake: taking 9 from 12, which leaves 3 — only divisible by 1. The 9 "starved" the remaining amount, forcing three inefficient 1-yen withdrawals. The optimal takes 6 from 12, leaving 6 — itself a valid denomination. One clean step instead of three.

Why Greedy Fails Here

The coin change greedy works on canonical coin systems — systems where the largest-first strategy is always optimal. US coins (1¢, 5¢, 10¢, 25¢) are canonical because each large denomination is an exact multiple of several smaller ones, so "trading down" is never cheaper.

Powers of 6 mixed with powers of 9 are not canonical. The denominations 6 and 9 are coprime — neither divides the other — so they compete for the same space. When greedy commits to 9, it leaves a remainder that 6 could have handled cleanly. The large denomination starves the remainder, forcing a cascade of expensive 1-yen fills.

Here's the specific failure: 9 + 1 + 1 + 1 = 12 (4 ops) vs 6 + 6 = 12 (2 ops). Greedy never considers two 6s because it already committed to 9.

The DP Solution

When greedy fails, the most common fix is Dynamic Programming.

Define dp[i] = minimum operations to withdraw exactly i yen.

Base case: dp[0] = 0 (zero withdrawals needed for 0 yen).

Transition: for each amount i, try every denomination d that fits: dp[i] = min(dp[i], dp[i - d] + 1).

The recurrence says: to get i yen, pick any valid denomination d, then optimally withdraw i-d yen.

Let's trace for N = 12, denominations = {1, 6, 9}:

i Best via d=1 Best via d=6 Best via d=9 dp[i]
0 — — — 0
1 0+1=1 — — 1
2 1+1=2 — — 2
3 2+1=3 — — 3
4 3+1=4 — — 4
5 4+1=5 — — 5
6 5+1=6 0+1=1 — 1
7 1+1=2 1+1=2 — 2
8 2+1=3 2+1=3 — 3
9 3+1=4 3+1=4 0+1=1 1
10 1+1=2 4+1=5 1+1=2 2
11 2+1=3 5+1=6 2+1=3 3
12 3+1=4 1+1=2 3+1=4 2

dp[12] = 2. Two withdrawals of 6 yen each. Greedy said 4 (it picks 9 + 1 + 1 + 1). DP is correct.

Stare at the d=6 column for i=12: it reads dp[6] + 1 = 1 + 1 = 2. The DP traced back through dp[6], which itself used denomination 6. Two clean hops. That's the power of optimal substructure — the DP builds from the bottom up, never committing to a denomination prematurely.

When Does Greedy Fail? Three Patterns

1. Non-canonical coin systems

If denominations aren't carefully designed (like mixed powers), use DP. The test: can you find any i where greedy does worse than DP because it committed to "wrong" large coins?

2. "No adjacent elements" constraints

Consider: from an array, pick non-adjacent elements to maximize the sum. Array: [10, 20, 15]. - Greedy picks 20 (the max). Now the neighbors 10 and 15 are blocked. Total = 20. - Optimal: 10 + 15 = 25. Greedy loses.

Why? Picking the local max blocks two neighbors, whose combined value might exceed it. Greedy can't see this tradeoff.

3. Future decisions depend on past choices in a complex way

If choosing item A now prevents you from choosing items B and C later, and B + C > A, greedy fails. This is the matroid structure breaking down.

The matroid test (intuitive): Greedy is guaranteed optimal when: if you have a valid solution of size k and another valid solution of size k+1, you can always extend the smaller one by adding one element from the larger one. When this "exchange property" breaks (like "no adjacent elements"), greedy fails.

Stress Testing: Your Safety Net

Even when you think greedy works, stress test it.

for (int amount = 1; amount <= 1000; amount++) {
    int greedyAnswer = greedyCoinChange(amount, denominations);
    int dpAnswer = calculateMinOperations(amount, denominations);
    if (greedyAnswer != dpAnswer) {
        cout << "FAIL at n=" << amount
             << " greedy=" << greedyAnswer
             << " dp=" << dpAnswer << "\n";
        break;
    }
}

Running this on the Strange Bank problem immediately reveals n=12 as a failing case. You'd catch this in 30 seconds instead of getting WA on submission.

The rule: If you can't prove your greedy works in 5 minutes, write the stress test first.

The Code (DP Solution)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int targetAmount;
    cin >> targetAmount;

    vector<long long> validDenominations = {1};
    for (long long powerOfSix = 6; powerOfSix <= targetAmount; powerOfSix *= 6) {
        validDenominations.push_back(powerOfSix);
    }
    for (long long powerOfNine = 9; powerOfNine <= targetAmount; powerOfNine *= 9) {
        validDenominations.push_back(powerOfNine);
    }

    auto calculateMinOperations = [&](int amount, const vector<long long>& denominations) {
        vector<int> minOperations(amount + 1, 1e9);
        minOperations[0] = 0;

        for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
            for (long long denom : denominations) {
                if (denom <= currentAmount) {
                    minOperations[currentAmount] = min(minOperations[currentAmount], minOperations[currentAmount - denom] + 1);
                }
            }
        }
        return minOperations[amount];
    };

    cout << calculateMinOperations(targetAmount, validDenominations) << "\n";
    return 0;
}

The denominations list: We generate 1 plus all powers of 6 up to n (at most log₆(n) ≈ 7 values) plus all powers of 9 up to n (at most log₉(n) ≈ 6 values). So the inner loop runs at most ~14 times. Total complexity: O(N × 14) = O(N). Perfectly fine for N ≤ 100,000.

The Key Takeaway

If you can't prove your greedy works — either by exchange argument or by "greedy stays ahead" induction — stress test it against brute force on small inputs. If it fails on any case, switch to DP.

This chapter introduced the exchange argument — swap two adjacent elements, show the result doesn't worsen. The remaining proof techniques are covered in the next chapters:

  1. Greedy stays ahead (Chapter 3): at every step, greedy is at least as far along as OPT
  2. Invariant-based proofs (Chapter 4): the greedy maintains a property that guarantees optimality

Want to Go Deeper?

The "matroid exchange property" we used above is just the surface. There's a rich mathematical theory — greedoids — that explains exactly which problems yield to greedy and which don't. Prim's and Dijkstra's are NOT matroids, but they ARE greedoids, which is why greedy still works for them.

Chapter 10 ("Mathematical Foundations") covers the full theory: formal definitions, the complete hierarchy (matroids ⊂ greedoids ⊃ antimatroids), the greedy optimality theorem, and how to classify any algorithm into its exact structure type.

Try It

The starter code is the correct DP solution. Test it:

Input: 48
Output: 3

Input: 12
Output: 2

Input: 100000
Output: ?  (figure it out: 100000 = 6^? + ... use the code)

Challenge: Modify the code to also print the denominations used (not just the count). This requires tracking which denomination was used at each dp[i].

Harder challenge: Is there a greedy solution for this specific denomination system? Think about when powers of 6 and powers of 9 overlap (6^2=36, 9^2=81, 6^3=216, 9^3=729 — they never overlap except at 1). Does this help? (Spoiler: no, the interactions still cause issues.)

Problems

Problem Link Difficulty Note
ABC099C — Strange Bank atcoder.jp/contests/abc099/tasks/abc099_c 300pts Greedy FAILS — use DP
LC 455 — Assign Cookies leetcode.com/problems/assign-cookies Easy
LC 860 — Lemonade Change leetcode.com/problems/lemonade-change Easy
LC 881 — Boats to Save People leetcode.com/problems/boats-to-save-people Medium