Find the Duplicate Number

nums has n + 1 values, each between 1 and n, so exactly one value is repeated (it may appear more than twice). Return that value without changing nums and with O(1) extra memory.

Examples

Example 1

Input:

find_duplicate([1, 3, 4, 2, 2])

Output:

2

Example 2

Input:

find_duplicate([3, 1, 3, 4, 2])

Output:

3

Constraints

• 2 <= len(nums) <= 200001
• 1 <= nums[i] <= n where n = len(nums) - 1
• Exactly one value appears more than once; all others appear once.