Missing Number in AP

Problem Statement

Given an array that represents an Arithmetic Progression (AP) with one missing element, find the missing number. The array is sorted and the common difference can be calculated from the first and last elements.

Constraints:

• 3 ≤ n ≤ 10^5
• Array is sorted
• Exactly one element is missing
• The missing element is not the first or last element

Example:

• Input: arr = [2, 4, 8, 10, 12, 14]
• Output: 6
• Explanation: The complete AP is [2, 4, 6, 8, 10, 12, 14]. Missing element is 6.

Example 2:

• Input: arr = [1, 6, 11, 16, 21, 31]
• Output: 26
• Explanation: Common difference = 5. Missing element between 21 and 31 is 26.

Approach 1: Brute Force (Linear Search)

Intuition

Calculate the expected common difference and scan through the array to find where the difference doesn't match.

Algorithm

1. Calculate common difference: d = (last - first) / n
2. Traverse array and check if arr[i+1] - arr[i] == d
3. If not, the missing element is arr[i] + d

public class Solution {
    public int findMissingBrute(int[] arr) {
        int n = arr.length;
        
        // Calculate common difference
        int d = (arr[n - 1] - arr[0]) / n;
        
        // Special case: d = 0
        if (d == 0) return arr[0];
        
        // Linear search for missing element
        for (int i = 0; i < n - 1; i++) {
            if (arr[i + 1] - arr[i] != d) {
                return arr[i] + d;
            }
        }
        
        return -1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Linear scan through array
• Space Complexity: O(1) - Only using variables

Approach 2: Binary Search (Optimal)

Intuition

For each index i, the expected value is arr[0] + i * d. If arr[i] equals the expected value, the missing element is on the right. If arr[i] exceeds the expected value, the missing element is on the left or at the current position.

Key Observations:

1. Expected value at index i: arr[0] + i * d
2. If arr[mid] == expected[mid], missing is in right half
3. If arr[mid] > expected[mid], missing is in left half (including mid)
4. Binary search to find the first position where arr[i] > expected[i]

Algorithm

1. Calculate common difference d
2. Binary search for the first index where arr[i] != expected[i]
3. Return the expected value at that position

public class MissingInAP {
    public int findMissing(int[] arr) {
        int n = arr.length;
        
        // Calculate common difference
        int d = (arr[n - 1] - arr[0]) / n;
        
        // Special case: constant AP
        if (d == 0) return arr[0];
        
        int low = 0, high = n - 1;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            
            // Expected value at index mid
            int expected = arr[0] + mid * d;
            
            if (arr[mid] == expected) {
                // Missing element is on the right
                low = mid + 1;
            } else {
                // Missing element is on the left (or at mid)
                high = mid;
            }
        }
        
        // low is the first index where arr[low] != expected
        return arr[0] + low * d;
    }
    
    public static void main(String[] args) {
        MissingInAP solver = new MissingInAP();
        int[] arr = {2, 4, 8, 10, 12, 14};
        System.out.println(solver.findMissing(arr));  // Output: 6
    }
}

Dry Run Example

Alternative: Using Formula

Complexity Analysis

• Time Complexity: O(log n) - Binary search
• Space Complexity: O(1) - Only using variables

Edge Cases

1. Negative Common Difference

2. Large Numbers

3. Single Step Missing

Variant: Multiple Missing Elements

Key Takeaways

1. Common Difference Calculation: d = (last - first) / n where n is the current array length
2. Binary Search Insight: Compare actual vs expected value at each index
3. Expected Value Formula: expected[i] = arr[0] + i * d
4. Search Property: If arr[mid] matches expected, missing is on right; otherwise on left
5. Edge Cases: Handle constant AP (d=0), negative differences, and overflow
6. Formula Approach: Can also solve using sum formula, but that's O(n)
7. Pattern Recognition: Binary search on sorted arrays with predictable structure