The Missing Number
The puzzle
A bag holds the numbers 1 to 100 on separate tickets, except that exactly one ticket has been removed.
You may look at each remaining ticket once, in any order, and you may keep a single running total. Which number is missing? Suppose your total comes to 5017.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
You already know what the total would have been if nothing were missing.
Hint 2
A missing number is the difference between what you expected and what you got.
Show the answer Hide the answer
33. The full total is 5050, and 5050 - 5017 = 33.
How to get there
The sum of 1 to 100 is 100 x 101 / 2 = 5050.
Adding the tickets you actually have gives 5017.
Everything present cancels, so the gap is the missing ticket: 5050 - 5017 = 33. One pass, one running total, no sorting and no second look.
The technique worth keeping
An invariant you can compute both ways turns a search into a subtraction. The same trick with a running XOR instead of a sum finds the missing number without any risk of overflow.