Description
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. Find and return this repeated number using O(1) extra space.
Examples
Input:
nums = [1,3,4,2,2]Output:
2Explanation:
2 is the repeated number.
Input:
nums = [1,1,2,3,4,5]Output:
1Explanation:
The array contains 6 elements (n+1 where n=5) with values in range [1,5]. The number 1 appears twice at positions 0 and 1, making it the duplicate.
Input:
nums = [2,5,9,6,9,3,8,9,7,1]Output:
9Explanation:
The array contains 10 elements (n+1 where n=9) with values in range [1,9]. The number 9 appears three times at positions 2, 4, and 7, making it the duplicate number.
Constraints
- •
1 ≤ n ≤ 10⁵ - •
nums.length == n + 1 - •
1 ≤ nums[i] ≤ n