Find the Duplicate Number
MediumLinked List
You are given an array nums of length n + 1 where every value is an integer in the range [1, n]. By the pigeonhole principle at least one value must repeat, and here exactly one value is repeated. It may appear two or more times (in which case some other values in 1..n will be missing).
Return the repeated value.
Your solution must not modify nums and should use only constant extra space. Aim for better than O(n^2) time.
Example 1
- Input:
- nums = [4, 1, 3, 4, 2]
- Output:
- 4
- Explanation
- The array has 5 slots, so values are in 1..4. Each of 1, 2, 3 appears once and 4 appears twice.
Example 2
- Input:
- nums = [2, 5, 2, 1, 2, 3]
- Output:
- 2
- Explanation
- Values are in 1..5. The value 2 fills three slots, which is why 4 never appears. The repeated value can occur more than twice.
Example 3
- Input:
- nums = [1, 1]
- Output:
- 1
- Explanation
- With two slots the only allowed value is 1, so it must be the repeat.
Constraints
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= n- Exactly one value appears more than once