432. Find the Only Repeating Element

Given a sorted array nums of length n+1 containing integers from 1 to n with exactly one integer appearing twice, find and return the duplicate number. Solve in O(n log n) using binary search on the value range.

Input: A sorted integer array nums of length n+1 with values in [1, n].

Output: The single duplicate integer.

Examples

Input: [1,2,3,4,4,5]
Output: 4
Explanation: Count of elements ≤ 4 is 5 > 4, so duplicate is in [1..4]. Narrow down to find 4.

Input: [1,1,2,3,4]
Output: 1
Explanation: Count of elements ≤ 1 is 2 > 1 → duplicate is 1.

Input: [1,2,2,3,4,5]
Output: 2
Explanation: Count ≤ 2 is 3 > 2 → check left half → duplicate is 2.

Constraints

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= nums.length - 1
• Exactly one duplicate
• Array is sorted

Asked by