Find the Duplicate Number

Problem

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 nums and uses only constant extra space.

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

 

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = nums[0]; // tortoise
    let fast = nums[0]; // hare

    // find intersection of slow and fast
    do {
        slow = nums[slow]; // one step at a time
        fast = nums[nums[fast]]; // two steps at a time
    } while (slow !== fast);

    // find entry point of cycle
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

We will implement Floyd's cycle detection algorithm. By the pigeonhole principle (due to the duplicate element) there must exist a cycle in nums. More specifically, the entry (ie. starting) point of this cycle is actually the duplicate value (since there are at least two i, j such that nums[i] = nums[j]).

Proof

Let F denote the distance from the start to the entrance of the cycle, C denote the length of the cycle, a denote the distance from the entrance to the intersection of slow and fast.

Notice that fast moved a total of F + nC + a distance (where nC is the number of complete cycles it traversed), and slow moved a total of F + a distance. Since fast moves at twice the pace of slow, it must be that 2(F + a) = F + nC + a => F + a = nC. Observe that:

• slow starts again at the beginning, when it moves F steps, it reaches the entry point.
• fast continues from the intersection point a, when it moves F steps, it is now at position F + a, which is equal to nC by our previous result, and so it is also at the entry point (ie. nC % C = 0).

Thus, when fast and slow meet again (by going one step at a time), they must meet at the entrance of the cycle (ie. the duplicate value).