501. Find the Duplicate Number (Binary Search on Value)

Given an array of n+1 integers where each value is in the range [1, n], at least one value is repeated. Using binary search on the value range (without modifying the array and in O(1) extra space), return a repeated value. The input array is guaranteed to contain a repeat. Input: an array of integers.

Input: An array of integers in [1, n].

Output: Integer — a repeated value.

Examples

Input: [1,3,4,2,2]
Output: 2
Explanation: 2 is repeated.

Input: [3,1,3,4,2]
Output: 3
Explanation: 3 is repeated.

Input: [1,1]
Output: 1
Explanation: 1 is repeated.

Constraints

• 2<=n+1<=10^5
• values in [1, n]
• at least one repeat

Asked by