Solution: Find the Duplicate Number

This solution involves two key steps. First, we’ll identify the cycle, confirming the duplicate number’s existence. Next, we’ll locate the entry point of this identified cycle, which represents the duplicate number in the array.

The fast and slow pointers technique detects such cycles efficiently, where one pointer takes one step at a time and the other advances by two steps. Initially pointing at the start of the array, the position of each pointer for the next step is determined by the current value they are pointing to. If a pointer points to the value 5 at index 0, its next position will be index 5. As the pointers traverse the array, if there’s a cycle, both pointers will eventually catch up. This is because, in the non-cyclic part, the distance between the pointers increases by one index in each iteration. However, once both pointers enter the cyclic part, the fast pointer starts closing the gap on the slow pointer, decreasing the distance by one index each iteration until they meet. Once the duplicate number is confirmed, we reset one of the pointers to index 0 while the other stays at the position where the pointers were met. Then, both pointers move one step at a time until they meet again. With this positioning and pace of pointers, it’s guaranteed that pointers will meet at the starting point of the previously identified cycle corresponding to the duplicate number.

Now, let’s look at the detailed workflow of the solution:

For this problem, the duplicate number will create a cycle in the nums array. The cycle in the nums array helps identify the duplicate number.

To find the cycle, we’ll move in the nums array using the $f(x) = nums[x]$, where $x$ is the index of the array. This function constructs the following sequence to move:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space x, \space nums[x], \space nums[nums[x]], \space nums[nums[nums[x]]], \space ...$ ...