An array holds n + 1 integers, each between 1 and n. By the pigeonhole principle at least one value appears twice. Assume exactly one value is duplicated (it may appear more than twice).
Find it with these constraints:
- O(1) extra space.
- Do not modify the array.
- Faster than O(n^2) time.
Example: [3, 1, 3, 4, 2] has n = 4, and the answer is 3.
Sorting is out (it modifies the array or needs extra space). A hash set is out (extra space). Think about what the values mean as indices.
Spoilers in replies, please. Bonus for a proof that your method terminates.