Missing element of AP

JavaView on GFG

Intuition

Find missing element in arithmetic progression. Binary search on expected vs actual difference.

Algorithm

1Common diff d = (arr[n-1] - arr[0]) / n. Binary search: if arr[mid] == arr[0]+mid*d: missing in right half. Else left half.

Common Pitfalls

•Exactly one element is missing. Compute d carefully. Binary search on index deviation.

Missing element of AP.java

Java

// Approach: Binary search for the position where the AP formula breaks (arr[mid] != arr[0] + mid * d).
// Time: O(log n) Space: O(1)
class Solution {
    public int findMissing(int[] arr) {
        int n = arr.length;
        int diff1 = arr[1] - arr[0];

        if (n == 2)
            return arr[1] + diff1;

        int diff2 = arr[2] - arr[1];
        int diff = Math.min(diff1, diff2);

        if (diff == 0)
            return arr[0];

        int l = 0, h = n - 1;
        
        while (l <= h) {
            int m = (l + h) / 2;

            int expectedPos = (arr[m] - arr[0]) / diff;
            int actualPos = m;

            if (actualPos < expectedPos)
                h = m - 1;
            else
                l = m + 1;
        }

        if (l == n)
            return arr[n - 1] + diff;

        return arr[0] + diff * l;
    }
}

Was this solution helpful?