Given an integer array arr of length n+1, where each element is in the range [1, n] inclusive, and exactly one integer occurs more than once, return the repeated integer. The array must not be modified and only constant extra space may be used.
Example 1
Input: [5,1,2,3,4,5]
Output: 5
Explanation: 5 is the only repeated integer.
Example 2
Input: [2,4,1,3,2]
Output: 2
Explanation: 2 is the only repeated integer.
Example 3
Input: [6,6,1,2,3,4,5]
Output: 6
Explanation: 6 is the only repeated integer.
Constraints
Case 1
Input: [7,3,1,2,4,5,6,7]
Expected: 7
Case 2
Input: [1,2,3,4,5,6,1]
Expected: 1
Case 3
Input: [4,2,1,3,4]
Expected: 4
Case 4
Input: [9,8,7,6,5,4,3,2,1,9]
Expected: 9
Case 5
Input: [10,1,2,3,4,5,6,7,8,9,10]
Expected: 10