Statement

Given an array of positive numbers, nums, such that the values lie in the range $[1, n]$, inclusive, and that there are $n+1$ numbers in the array, find and return the duplicate number present in nums. There is only one repeated number in nums.

Note: You cannot modify the given array nums. You have to solve the problem using only constant extra space.

Constraints:

• $1 \leq n \leq 10^3$
• nums.length $= n + 1$
• $1 \leq$ nums[i] $\leq n$
• All the integers in nums are unique, except for one integer that will appear more than once.

Examples