Given an array nums containing n + 1 integers where each integer is between 1 and n inclusive, prove that at least one duplicate number exists and return that duplicate. The solution should use constant extra space.
nums = array of integers
the duplicate value
Example 1:
Input:
nums = [1,3,4,2,2]
Output:
2
Explanation:
2 appears twice.
Example 2:
Input:
nums = [3,1,3,4,2]
Output:
3
Explanation:
3 is the duplicate.