A fare machine stocks denominations 1, 3 and 4 - why can largest-first change-making use more coins than necessary?
answer
- Try a set that is not everyday currency
- Denominations 1, 3 and 4; target 6
- What remainder does taking the 4 leave?
- 2 can only be paid in unit coins
- Three coins greedily, two coins optimally
basics
~20 sFor an amount of 6, largest-first takes 4, then 1 and 1 - three coins - while 3 + 3 uses only two. Taking the biggest coin left a remainder of 2 that only unit coins could pay.
solid answer
~50 sLargest-first is a greedy strategy: at each step take the biggest denomination that still fits. With denominations 1, 3 and 4 and a target of 6, it takes the 4, leaving a remainder of 2 that nothing but unit coins can cover, so it returns `4 + 1 + 1` - three coins. The true minimum is `3 + 3`, two coins. The choice was locally best and globally wrong: the 4 maximised immediate progress but left the remainder in a shape the rest of the denomination set could not use. Everyday currency systems happen to be *canonical* - largest-first is optimal for them - which is exactly why the strategy looks universally safe. For an arbitrary denomination set you either prove that set is canonical or you compute the minimum exactly instead of committing coin by coin.
code
pseudocode · 13 lines// d holds the denominations, sorted descending
count = 0
remaining = amount
for i in 0..length(d)-1
while remaining >= d[i]
remaining = remaining - d[i]
count = count + 1
// d = [4, 3, 1], amount = 6
// take 4 -> remaining 2, count 1
// 3 no longer fits
// take 1 -> remaining 1, count 2
// take 1 -> remaining 0, count 3
// returns 3; the optimum is 2 (3 + 3)go deeper
Memorise one counterexample you can state in ten seconds - denominations 1, 3 and 4, amount 6, greedy gives three coins and the optimum is two. Being able to produce it on demand is what the question is testing.
Explain the mechanism, not just the numbers: taking the largest coin leaves a remainder that the rest of the set cannot cover cheaply. Be ready to say that greedy is optimal precisely for canonical denomination sets.
Show that you would verify rather than assume. Say how you would test a given denomination set for greedy-optimality, and note the second failure grade - no unit coin means greedy can return nothing where a valid combination exists.
Own the framing that the denomination set is an input someone chose, and choosing it well makes the cheap algorithm provably correct. Treat 'which numbers do we stock' as a decision with an algorithmic consequence, not a fixed constraint.
## The strategy under test Largest-first change-making is a greedy algorithm. To pay an amount, repeatedly take the largest denomination that still fits, subtract it, and continue until the remainder reaches zero. It makes one pass over the denominations, needs no memory beyond a running remainder, and is the first idea nearly everyone has. The interesting question is never whether it runs - it is whether the combination it produces uses the *fewest* coins. ## The counterexample Take a fare machine stocked with denominations 1, 3 and 4, and ask it to return 6. - Largest-first: 4 fits, so take it. Remainder 2. The 3 no longer fits, so take 1, then 1. Result: `4 + 1 + 1`, three coins. - Optimum: `3 + 3`, two coins. The greedy answer is valid - it sums to 6 - but it is not minimal. This tiny set is the standard demonstration that largest-first change-making is not a general algorithm, only a heuristic that happens to be exact on some denomination sets. ## Why the local choice was wrong A greedy algorithm is correct when its first move is contained in *some* optimal solution, and the same reasoning then applies to what remains. That is the greedy-choice property. Here the property fails outright. Taking the 4 leaves a remainder of 2, and 2 cannot be built from 3s or 4s, so the algorithm is forced all the way down to unit coins. The 4 was the largest single step available, and taking it destroyed the structure - a remainder divisible by 3 - that the cheaper solution depended on. That is the general failure mode of greedy reasoning, and it is worth stating in exactly these terms in an interview: a choice that maximises immediate progress can eliminate the arrangement the remaining choices needed. "Bigger step now" and "fewer steps overall" are different objectives, and they only coincide when the problem has a property you can point at. ## Feasible is not optimal - and sometimes not even feasible Because the set contains a 1, largest-first here always terminates with *some* valid combination; the unit coin can absorb any remainder. Drop the 1 and it can fail to find an answer that exists at all. With denominations 3 and 4 and a target of 6, greedy takes the 4, is left with 2, and has nothing that fits - yet `3 + 3` pays the amount exactly. So there are two distinct failure grades: returning a suboptimal answer, and returning no answer when one exists. Candidates routinely notice the first and miss the second. ## Canonical denomination sets A denomination set for which largest-first is optimal at *every* amount is called canonical. Most real currency systems - denominations like 1, 2, 5, 10, 20, 50 - are canonical, which is why the strategy feels obviously right to anyone who has ever made change at a till. Sets designed for other reasons (vending stock, chip counts, packaging units, historical currencies) frequently are not. Importantly, "is this set canonical?" is a decidable question, not a matter of taste. If a counterexample exists, the smallest one is bounded in terms of the largest denominations, so a finite search settles it, and polynomial-time tests for canonicity are known. When an interviewer hands you a fixed, unusual denomination set, the strong answer is: greedy may well be optimal here, and it is checkable - either exhaustively below that bound, or by differential testing against an exact method on small amounts. ## When greedy is not enough If the set is not canonical, the minimum-coin count has to be computed by a method that considers every way of decomposing the amount rather than committing one coin at a time. That method is exact, and its cost grows with the numeric amount as well as the number of denominations - which is why it is the right answer for a fare machine handling amounts under a few hundred, and a genuine problem when amounts run to the billions. ## What to say in the room When asked "does greedy work here?", do not answer yes or no from intuition. Answer with the shape of the argument: greedy is optimal for change-making exactly when the denomination set is canonical; here is a three-coin set where it is not; and here is how I would check the set I have been given. That answer distinguishes someone who has memorised "greedy is fast but sometimes wrong" from someone who knows *what* to check.
- Can largest-first ever fail to return any combination at all, not merely a suboptimal one?Yes, as soon as the set has no unit coin. With denominations 3 and 4 and a target of 6, greedy takes the 4, is left with a remainder of 2, and nothing fits - yet 3 + 3 pays the amount exactly. Having a 1 in the set guarantees the algorithm always finishes with some valid combination, but it guarantees nothing at all about that combination being minimal.
- Why does largest-first work perfectly for the currency in your pocket?Because those denomination sets are canonical: for every amount, the largest coin that fits belongs to some minimal combination. That is a property of the specific numbers chosen, not of the algorithm. Currency systems are designed partly so that people can make change greedily in their heads. Take those numbers away and the strategy has no remaining justification.
- Given an unfamiliar denomination set, how would you find out whether greedy is safe?Search for a counterexample rather than arguing about it. Compute the exact minimum for every amount up to a bound derived from the largest denominations and compare it against the greedy count; if a counterexample exists at all, the smallest one falls inside that range. A quick differential test against an exact method on small amounts catches almost every non-canonical set in seconds.
Filling a suitcase by packing the biggest object first: it fits, but it can leave a gap in exactly the shape nothing else has.
saying these in an interview costs you the question
- Says largest-first change-making is always optimal
- Assumes any denomination set behaves like everyday currency
- Confuses producing a valid answer with producing a minimal one
- Claims greedy always finds a combination when one exists
- Argues greedy must be right because it passed the sample amounts