medium

Find the Duplicate Number

An array of n + 1 integers holds values in the range 1..n, so at least one value repeats. Exactly one value is duplicated (possibly many times). Find it without modifying the array and using constant extra space.

Constraints

1 ≤ n ≤ 10^5
nums.length = n + 1
1 ≤ nums[i] ≤ n
Only one repeated value

Examples

in: nums = [1,3,4,2,2]

out: 2

in: nums = [3,1,3,4,2]

out: 3

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.