Problem Overview

You are given an array nums containing n + 1 integers.
Each integer is in the range [1, n].

There is exactly one number that appears more than once.
Your task is to return that number.

Restrictions:

• You are not allowed to modify the array.

• You must use constant extra space.

• The solution must run in linear time.

Why a Duplicate Must Exist

The array contains n + 1 numbers, but all values are limited to the range [1, n].

This means:

• There are more elements than possible distinct values.

• By the pigeonhole principle, at least one value must repeat.

So a duplicate is guaranteed.

Approach 1: Brute Force Comparison (O(n²))

Steps:

1. Compare every element with every other element.

2. If two values are equal, return the duplicate.

This method works, but it is far too slow for large inputs.

Approach 2: Sorting the Array (O(n log n))

Steps:

1. Sort the array.

2. Scan adjacent elements.

3. If two consecutive values are equal, that value is the duplicate.

Problem:

• Sorting modifies the array.

• Extra space may be required.

This approach violates the problem constraints.

Approach 3: Cycle Detection (O(n) Time, O(1) Space)

This is the correct and optimal solution.

Key Observation

Each value in the array can be treated as a pointer to another index.

Because:

• Values range from 1 to n

• Indices also range from 0 to n

This creates a structure similar to a linked list with a cycle.
The duplicate number is the entry point of the cycle.

Step 1: Find the Meeting Point

Use two pointers:

• slow moves one step at a time.

• fast moves two steps at a time.

They will eventually meet inside the cycle.

Step 2: Find the Start of the Cycle

Reset slow to the beginning.
Move both pointers one step at a time.
The point where they meet again is the duplicate number.

Final Code (Cycle Detection)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};