Code RoomGreedy change counterexample
HardPrep Room Coding #4870

Greedy change counterexample

CodingAlgorithms & data structuresMid–Staff~35 min

A game economy lists its token denominations in token_values, always including 1, all distinct and positive, in no particular order. The payout routine settles an amount by repeatedly handing over the largest token worth no more than what is still owed, which always terminates because 1 is in the set. That shortcut is not always thrifty: for some denomination sets there are amounts it settles with more tokens than the fewest possible. Return the smallest positive amount where the shortcut hands over more tokens than the fewest possible, or 0 when no such amount exists. You may rely on one published fact: if such an amount exists at all, the smallest one is strictly below the sum of the two largest denominations, so the search is finite.

Implement
smallest_greedy_failure(token_values: list[int]) → int
Examples
in[[1,3,4]]out6
in[[25,1,10,5]]out0
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 35 min
InputExpectedGot
[[1,3,4]]6not run yetsample
[[25,1,10,5]]0not run yetsample