Greedy: Canonical Coin Change

Intermediate Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

Canonical Coin Change with denominations 1, 5, 10, 25: always choose the largest possible coin. For this system, Greedy is optimal.

Arbitrary denominations (not greedy): Coin Change [1].

Where used

Everyday example and counterexample machine: Greedy fails with non-canonical coin systems. It trains distrust of local choices without proof.

Depth

In the Greedy coin change, the largest suitable coin is chosen each time. For some coin systems, this always provides a minimal number of coins; such systems are called canonical. The common euro denominations are designed so that the rule works for typical integer amounts.

For arbitrary denominations, the rule is not reliable. A single counterexample is sufficient to disprove the general validity. Dynamic programming, on the other hand, can compute the smallest number of coins for all amounts up to the target and is also useful for systematically checking a coin system in a finite range.

Difficulty levels

Execute the Greedy selection for a given coin system.
Disprove a coin system with a counterexample.
Compare Greedy results and DP optimum over many target amounts.

Pitfalls

Just because the rule works for multiple tested amounts does not constitute a general proof. Additionally, reachability and a coin with a value of one must be considered separately from the optimality question.

Sources

[1]https://leetcode.com/problems/coin-change/Return to text

University approvals: 0

Tasks

Question 1

Implement minCoins(amount) for coins 25, 10, 5, 1.

Hint

Integer division / and remainder % operate directly with int. Coin values can be in an int[] literal.

public class Coins {
  public static int minCoins(int amount) {
    // TODO
    return 0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Question 2

What does this case show for coins with values 1, 3, and 4 when changing the amount 6?

The largest matching coin leads to more coins here than any other option.

Each coin selection requires exactly four coins.

The amount cannot be represented with this system.

The greedy rule and any optimal solution must necessarily start with 4.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy