The array has n plus 1 numbers, each between 1 and n, so at least one value repeats. Find the repeated number without changing the array and with constant extra space.
DSA Animator › DSA Revision › Bit Manipulation › Find the Duplicate Number
Remember: extra copies show up as extra ones in their bit positions. Floyd’s cycle detection is the other O of 1 space solution. The video solves Find the Duplicate Number (LeetCode 287, Medium) with the Bit Counting pattern from the Bit Manipulation topic, and you can replay every step in the interactive Find the Duplicate Number animation.
The array has n plus 1 numbers, each between 1 and n, so at least one value repeats. Find the repeated number without changing the array and with constant extra space.
For 1, 3, 4, 2, 2, the answer is 2.
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.
n is 4, so the range is 1, 2, 3, 4. Bit 0: the array has 2 ones, and the range has 2, so this bit is 0. Bit 1: the array has 3 ones, from 3, 2 and 2, but the range has only 2. So bit 1 is set in the duplicate. Bit 2: both have 1, so it is 0. The duplicate is 010, which is 2.
In code, loop over bit positions. Count the bit in the array, and the bit in the numbers 1 to n. If the array count is larger, set that bit in the answer. It's O of n log n time and O of 1 space.
Remember: extra copies show up as extra ones in their bit positions. Floyd’s cycle detection is the other O of 1 space solution.