455. Find the Difference in Sorted Array of Consecutive Numbers

Given a sorted array that should contain consecutive integers but has exactly one number missing, find and return the missing number. The array may start at any integer. Solve in O(log n).

Input: A sorted integer array with consecutive values except one missing.

Output: The missing integer.

Examples

Input: [1,2,4,5,6]
Output: 3
Explanation: arr[2]=4 but expected arr[0]+2=3. Binary search finds gap at index 2.

Input: [10,11,13,14]
Output: 12
Explanation: arr[2]=13 but expected 12. Missing is 12.

Input: [-3,-2,-1,1]
Output: 0
Explanation: Expected consecutive from -3; 0 is missing.

Constraints

• 2 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• Sorted ascending
• Exactly one missing

Asked by