Find the Duplicate Number

Medium

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

Example 1

Input:  nums = [1,3,4,2,2]
Output: 2

Example 2

Input:  nums = [3,1,3,4,2]
Output: 3

Constraints

• 1 <= n <= 10^5
• nums.length == n + 1
• Only one repeated number, but it may appear more than once.