Given an array of integers nums containing n+1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums; return this repeated number. You must solve the problem without modifying the array and use only constant extra space.
nums = [1,3,4,2,2]2nums = [3,1,3,4,2]3nums has values 1..n in n+1 slots. Treating value as next-pointer creates a linked list with a cycle at the duplicate. The duplicate value is pointed to by two different indices, so it is the cycle entrance. Floyd's algorithm finds the cycle start in O(n) time and O(1) space — Phase 1 brings both pointers inside the cycle; Phase 2 (reset slow to start, advance both at same speed) guarantees they meet exactly at the cycle entrance.
Sorting changes the array, and a hash set uses extra space. We can compare bit counts instead.
For each bit position, count how many numbers in the array have that bit set. Also count how many numbers from 1 to n have that bit set. The duplicate adds extra ones in exactly the positions where its own bits are 1. So if the array count is bigger, that bit belongs to the duplicate.
Extra copies show up as extra ones in their bit positions. Floyd’s cycle detection is the other O(1) space solution.
Run the animation above on your own input, or watch the 1:35 video explanation of Find the Duplicate Number with a dry run and Java code.