Solution: Find the Duplicate Number

This solution involves two key steps: identifying the cycle and locating 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, both will eventually catch up because there’s a cycle. This is because, in the noncyclic 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 (usually the slow pointer) to index $0$ while the other stays at the position where the pointers met. Then, both pointers move one step at a time until they meet again. With this positioning and pace of pointers, pointers are guaranteed to meet at the cycle’s starting point, 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 ...$ ...