Missing number in an arithmetic progression
Problem
The array is an arithmetic progression with exactly one term missing from the middle. Return the missing term in O(log n) time.
Example 1
Input: [2, 4, 8, 10, 12, 14] Output: 6
Also asked as: Missing Number in AP
Test cases
Case 1
Input: [2,4,8,10,12,14] Expected: 6
Case 2
Input: [1,6,11,16,21,31] Expected: 26
Case 3
Input: [10,7,1] Expected: 4
Case 4
Input: [1,3,7] Expected: 5
View solutionHide solution1 approach
1. Binary search using the common difference
Time O(log n)Space O(1)
d = (last − first) / n (with one term missing there are n terms of an original n+1). The missing element is where a[mid] !== first + mid·d.
function missingInAP(a) { const n = a.length; const d = (a[n - 1] - a[0]) / n; // n gaps expected across n+1 terms let lo = 0, hi = n - 1; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] === a[0] + mid * d) lo = mid + 1; else hi = mid; } return a[0] + lo * d;}