Pigeons and holes
Find the repeated number in an unsorted list by searching the value range, counting how many entries fall at or below the middle. About 14 minutes.
Too many pigeons
A list has n + 1 numbers, each between 1 and n, so at least one number must repeat. The list is not sorted, and you are not allowed to change it. Where is the repeat?
Think of the values 1 to mid as mid holes. If more than mid entries fall in those holes, two of them share a hole, so a repeated value lies in 1 to mid. If not, the repeat must be in the values above mid.
count = sum(1 for v in nums if v <= mid) too_many = count > mid # pigeons win
Try the middle value, 3. How many entries are at most 3? Four of them (2, 3, 2, 1), which is more than 3. So the repeat is 3 or below.
In values 1 to 5, you count 7 entries that are at most 5. What does this tell you?
- AA repeat lies in the values 1 to 5, since 7 entries share 5 values
- BNothing, since counts don't prove repeats
- CThe repeat is above 5
Show the answer
A repeat lies in the values 1 to 5, since 7 entries share 5 values. More entries than values means two entries must be equal.
The repeated value
nums holds n + 1 whole numbers, each between 1 and n, and exactly one value occurs more than once (it may occur many times). The list may not be changed. Return the repeated value.
nums = [3, 1, 3, 4, 2] → 3
2 ≤ length ≤ 100,001 · every value is between 1 and length − 1