348. Missing Number in an Arithmetic Progression

An arithmetic progression of n+1 terms has exactly one term missing. Given the remaining n terms in their original AP order, find the missing term.

Input: The first line contains an integer n. The second line contains n space-separated integers, the remaining terms of the arithmetic progression in order. Output: Print a single integer - the missing term of the arithmetic progression.

3 <= n <= 10^5

This is another 'binary search on a boolean condition that flips exactly once' problem (matches expected value, until it suddenly doesn't) - recognizing this monotonic flip pattern is the key to applying binary search here at all.

Given an arithmetic progression with exactly one term missing, find that missing term. Brute force: Scan the array linearly, comparing each element to what it 'should' be based on the expected common difference - this costs O(n), correct but doesn't exploit binary search's ability to find the mismatch point faster. Optimised: Since every index BEFORE the missing term's position matches its expected value exactly, and every index AT OR AFTER it is systematically shifted, checking 'does arr[mid] match its expected value' at each step of a binary search directly narrows down to the exact break point in O(log n).

Compute the gap between every pair of consecutive given terms; in a valid sequence with exactly one term removed, all of these gaps equal the true common difference d except for one gap that equals 2d, straddling the missing term. For each candidate d drawn from these observed gaps, scan the whole array to check whether it's consistent with that difference and, if so, locate the single break point and interpolate the missing value. This works but repeats a full O(n) validation scan for potentially many candidate values of d. Time: O(n^2) Space: O(1)

Compute all n-1 gaps between consecutive given terms and use a hashmap to find which gap value occurs most often; since only one gap (around the missing term) differs from the true common difference d, the most frequent gap value is exactly d. With d determined in one pass, make a second linear pass over the array to find the position where the gap is 2d instead of d, and interpolate the missing value there. This replaces the repeated re-validation of the brute-force approach with a single frequency count followed by a single scan. Time: O(n) Space: O(n)

Since exactly one term is missing from an (n+1)-term arithmetic progression, the true common difference d can be computed directly in O(1) as (last - first) / n, using just the array's first and last given values and its length. With d known, every position before the missing term should satisfy arr[i] = first + i*d, and every position from the missing term onward is shifted by one extra step; binary search over the index for the first position where arr[i] no longer matches this formula, and the missing value is the formula's prediction at that boundary. This exploits the sequence's monotonic, formulaic structure to locate the break point in logarithmic time instead of scanning the whole array. Time: O(log n) Space: O(1)

1. Compute the common difference of the FULL (uninterrupted) progression as (last - first) / n, where n is the count of terms actually given (since one is missing from what would be n+1 terms). 2. Binary search for the first index where arr[i] no longer equals (first + i * diff) - that mismatch reveals exactly where the missing term should have been. 3. The missing value is simply the expected value at that position.

Time: O(log n) - one binary search after an O(1) common-difference computation. Space: O(1) - just a few pointer variables.

Test the missing term being the first or last of the full progression, n = 3 (smallest case), and n = 10^5 for performance.

Be ready to state the common-difference formula precisely (dividing by n, the GIVEN count, not n+1) - this is a subtle but crucial detail, since the full progression conceptually has n+1 terms but only n are actually provided.