Skip to content
AI360Xpert
Back to Linked List
Medium

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.

Examples

Input:nums = [1,3,4,2,2]
Output:2
The number 2 appears twice in the array.
Input:nums = [3,1,3,4,2]
Output:3
The number 3 appears twice.
Input:nums = [3,3,3,3,3]
Output:3
The number 3 appears multiple times.

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.

Floyd's Tortoise and Hare (Cycle Detection)

Approach

1. We can view the array as a linked list where the index represents a node and the value at that index represents the `next` pointer (`next = nums[index]`). 2. Because the array contains `n + 1` integers between `1` and `n`, there must be at least one duplicate, meaning multiple nodes point to the same next node. This guarantees a cycle. 3. We use Floyd's Cycle Detection algorithm. We initialize two pointers, `slow` and `fast`, both starting at the first element `nums[0]`. 4. We move `slow` one step (`nums[slow]`) and `fast` two steps (`nums[nums[fast]]`) until they meet. This proves there is a cycle. 5. To find the start of the cycle (the duplicate number), we move `slow` back to `nums[0]` and keep `fast` at the intersection point. 6. We then move both `slow` and `fast` one step at a time. The point where they meet again is the entrance to the cycle, which is our duplicate number.

Complexity Analysis

Time Complexity
O(N)
Space Complexity
O(1)

This approach satisfies the constraints of not modifying the array and using O(1) space.

Solution.java
class Solution {    public int findDuplicate(int[] nums) {        // Step 1: Find intersection point in the cycle        int slow = nums[0];        int fast = nums[0];                do {            slow = nums[slow];            fast = nums[nums[fast]];        } while (slow != fast);                // Step 2: Find the entrance to the cycle        slow = nums[0];        while (slow != fast) {            slow = nums[slow];            fast = nums[fast];        }                return slow;    }}