Missing number in an arithmetic progression

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}