Missing element of AP

JavaView on GFG

Problem Overview

Find missing element in arithmetic progression.

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?