73. Find the Duplicate Number

Given an array of integers nums containing n+1 integers where each integer is in the range [1, n], there is only one repeated number. Return this repeated number.

You must solve the problem without modifying the array and using only O(1) extra space.

Input: An array nums of length n+1 where values are in [1, n] with exactly one duplicate.

Output: Integer — the duplicate number.

Examples

Input: [1,3,4,2,2]
Output: 2
Explanation: Value 2 appears twice.

Input: [3,1,3,4,2]
Output: 3
Explanation: Value 3 appears twice.

Input: [1,1]
Output: 1
Explanation: Only two elements, 1 is repeated.

Constraints

• 1 <= n <= 10^5
• nums.length == n+1
• 1 <= nums[i] <= n
• Only one duplicate exists.

Asked by