LeetCode //C - 287. Find the Duplicate Number

287. Find the Duplicate Number

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

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

• $1<=n<=10^5$
• 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.

From: LeetCode
Link: 287. Find the Duplicate Number

Solution:

Ideas:

1. Initialization: Both the tortoise and the hare start at the first element (index 0).

2. Phase 1 - Detecting the cycle:

• The tortoise moves one step at a time (nums[tortoise]), while the hare moves two steps at a time (nums[nums[hare]]).
• If there’s a cycle (which there is, due to the duplicate), the hare will eventually meet the tortoise within this cycle, proving the cycle’s existence.

3. Phase 2 - Locating the cycle’s start:

• After the meeting, reset one of the runners to the start of the list (index 0), keeping the other at the meeting point.
• Move both at the same speed (one step at a time). The point at which they meet again is the start of the cycle, which corresponds to the duplicate number in the array.

Code:

int findDuplicate(int* nums, int numsSize) {
    // Phase 1: Finding the intersection point of the two runners.
    int tortoise = nums[0];
    int hare = nums[0];
    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    } while (tortoise != hare);

    // Phase 2: Find the "entrance" to the cycle.
    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return hare;
}