Medium · greedy

Minimum Coins

A cashier does not plan: they grab the biggest coin that fits, again and again. That strategy — take the best immediate step — is greedy, and for this coin system it is provably optimal.

At a glanceCount how many 25s fit, then 10s, then 5s, then 1s: <code>amount / 25</code> coins of 25, replace amount with <code>amount % 25</code>, and so on. Four lines, no search.

Problem

Input: One integer amount (1 ≤ amount ≤ 100000), the cents to pay.

Output: The minimum number of coins with values 25, 10, 5 and 1 that add up to exactly amount.

Samples:

Input	Output
`30`	`2`
`99`	`9`
`1`	`1`

Greedy is not a law of nature — it is a property of this coin system. After the solution you will meet a coin set where the same strategy fails, and that is the interview question hiding inside this problem.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Division is a batch operation

amount / 25 is how many 25-coins fit at once — you never need a loop over coins. After taking them, the remainder to pay is amount % 25. Repeat with 10, then 5; whatever is left is paid in 1s, and that final count is just the remainder itself.

Hint 2 — Why biggest-first is optimal here

In an optimal solution there are at most four 1s (five would make a 5), at most one 5 (two make a 10), and when a 25 fits, the mix 10+10+5 saves nothing over one 25 (10+10+5 = 25). Count each denomination up to those caps and everything above them must be 25s — which is exactly the greedy choice. The proof is the counting; greedy computes it in four lines.

Hint 3 — Know when greedy breaks

Run the same strategy on coins {4, 3, 1} for amount 6: greedy takes 4+1+1 = 3 coins, but 3+3 takes 2. Greedy is only guaranteed optimal for canonical systems like 25/10/5/1. If an interviewer asks whether it always works, that example is the answer.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;

    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;  amount %= 5;
    coins += amount;      // the rest is paid in 1s

    cout << coins << endl;
    return 0;
}

Greedy works here because the coin system lets it. When it does not — the {4, 3, 1} above, or the quirks of real currencies — you must search, and the standard upgrade is dynamic programming. Before that, meet another trade-search-for-structure idea: Range Sum Queries pays O(n) once and then answers every question in O(1), the same bargain greedy makes.

Deep dive

Why this works

Take the biggest coin that fits, repeat. For 25/10/5/1 this is provably optimal: an optimal solution never needs more than four 1s, one 5, or (when a 25 fits) two 10s plus a 5 — so everything above those caps must be 25s, which is exactly what greedy takes first.

The cost

Four divisions and four remainders: O(1) time and space, whatever the amount. The general version — arbitrary coins, is amount X payable — needs dynamic programming at O(amount × coins).

Where it goes wrong

Believing greedy is universally optimal. With coins {4, 3, 1} and amount 6 it pays 4+1+1 (three coins) where 3+3 takes two — greedy is only safe for canonical systems.
Looping coin by coin (while (amount >= 25) { coins++; amount -= 25; }) instead of dividing. Same answer, but / and % already are that loop, done in one step.

Next step

The pay-once-answer-many trade continues in Range Sum Queries — prepare once, then every query is O(1).

Two things to remember

Greedy = best immediate step; prove it per coin system, never assume it.
amount / c coins of c fit at once; the rest is amount % c.

🐞 This version fails — open it and try

Drops the leftover cents — the 1-coins never get counted

#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;
    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;
    cout << coins << endl;
    return 0;
}