Practice · 5 of 5
Broken Denominations
CHALLENGE
Difficulty: intermediate+25 XP
**Description:** Coins come in 1, 3, 4 (this odd system!). Pay exactly X
with the fewest coins. The always-take-largest greedy FAILS here — find
the true minimum.
**Input:** One integer X (1 ≤ X ≤ 10^6).
**Output:** One integer — the true minimum coin count.
**Example:** 6 → 2 (3+3, not 4+1+1).
*Insight:* with this system greedy needs proof you cannot give — a small
DP over amounts (module 15) solves it cleanly.
Press Submit to check your solution.
Back to lesson: Practice: Greedy Set