The Missing Number

  • Easy
  • Number puzzles
  • Tests: Comparing a total against the total it should have been

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.