Qm
Brainteasers

Find the duplicated number

algorithmssumspigeonholestreams

A list contains 101 numbers: every whole number from 1 to 100 appears exactly once, and one of those numbers appears a second time. The list is in random order and you may read it only once, keeping just one number in your head.

  1. How do you find the repeated number?
  2. Why must there be a repeated number at all, before you even look?
Show a hint

You know the sum of 1 to 100. What does the extra copy do to the total?

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Why the Naive Shuffle Is BiasedThe Bisection MethodDetecting Cycles in an Iterated SequenceDynamic Programming BasicsFinding the Median With Few Comparisons

Related questions

Find the missing number in one passWriting 100 as a sum of consecutive numbersEight batteries, four good, one flashlightA run of days that nets a multiple of nEvery year has a Friday the 13th
All questions →