My Favorite CS Puzzle

Some years ago I stumbled upon this CS puzzle:

Given an array of size n in which each of the values are integers from the range of 0 to n-2. You need to:

1. Show that at least one of the elements repeats itself
2. Find a duplicated element

Try solving it before continuing, But keep in mind that, according to this lecturer at Stanford, it took Donald Knuth himself 24 hours to solve.

Here is the leetcode version which is a bit different (in their case exactly one value can repeat itself), but the solution is the same.

This article gives, what I hope is, a simpler explanation of the solution using examples and interactions. Let me know what you think.

From this point on, there will be spoilers.

🤔 Isn't It Easy?

Well, it might seem easy at first, especially if there are no time and space constraints. You can do all sort of things, sort the array, use a dictionary, etc. But the question is asking for a solution that is both in O(n) time and O(1) space. That is not easy.

🐦 The Pigeonhole Principle

The first part of the question is to show that at least one of the elements repeats itself.

There's a basic, but powerful, mathematical principle called The Pigeonhole Principle: Visualize a wall with holes in it (a dovecote). Imagine there are n holes and m pigeons, while m > n. If all pigeons are to sit inside a hole, there must be at least one hole that has more than 1 pigeon in it.

It might sound somewhat trivial, but it can be used to answer some seemingly hard questions like:

Are there 2 people in Tel Aviv with the exact same number of hairs on their head?

Well, if I told you there are at most 300k hairs on a human head, and there are 450k people in Tel Aviv right now, then according to our principle, there must be at least 2 people with the exact same number of hairs on their head! Kinda surprising!

Back to the question - In our case, we have an array of length n with n-1 possible values (since their range is from 0 to n-2). So if we imagine each index as a pigeon and each value as a hole, we can see that at least one of the pigeons must share a hole with another pigeon, i.e. 2 indices share the same value, i.e. a value in the array repeats itself.

Here's a visualization of that:

Pick the array's length n=