Optimal Change for Any Under-$100 Bill

This brain teaser is about planning how to always give exact change in a worst-case scenario, under strict limits on denominations. It sits at the intersection of discrete math, number theory, and optimization, and is typical of the short, sharp puzzles used in quant interviews to test structured reasoning under pressure. It looks simple, but hides a subtle coverage question over all possible amounts.

It trains your sense of optimality, combinatorial counting, and your intuition for when a locally best decision is also globally best. It also develops your ability to reason about canonical currency systems and to translate an informal "always possible" requirement into a precise, exhaustive condition over a finite set of integers.

This matters for quant prep because market-making and trading roles constantly balance efficiency and completeness under constraints. Interviewers want to see if you can build a rigorous argument, handle edge cases, and communicate a clean, general conclusion from a seemingly small puzzle.

What it tests

This problem class is governed by the greedy algorithm for making change with fixed denominations. The principle is to always use the largest denomination possible at each step, then move to the next largest, and so on, until the desired amount is reached. This approach works optimally when the denominations are canonical, meaning no combination of smaller denominations can replace a larger one more efficiently. The reason this greedy method works is that each denomination is a multiple or near-multiple of the next smallest, so using the largest bills first minimizes the total count needed to reach any amount. The underlying structure is about covering all possible sums up to a target value using the fewest pieces, which is a classic coin change problem.