101. Find the Duplicate Number (Floyd's Cycle Detection)

Given an array of integers nums containing n+1 integers where each integer is in [1,n], there is exactly one repeated number. Return this number without modifying the array and using O(1) extra space.

Input: Array nums of length n+1 with values in [1,n], exactly one duplicate.

Output: Integer — the duplicate number.

Examples

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

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

Input: [1,1]
Output: 1
Explanation: 1 is the duplicate.

Constraints

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

Asked by