Missing Number in AP

The problem, simply

You get a sorted list of numbers that go up (or down) by the same step every time, except one number in the middle was taken out. Find the missing number.

A row like this is called an arithmetic progression. The missing number is never the first or the last one, so the first and last numbers are real and tell you the step.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the step, then walk the row and look for the one gap that is twice as big.

1. The full row had n + 1 numbers, so it had n steps. The step is d = (arr[n - 1] - arr[0]) / n.
2. Walk from left to right. The first time arr[i + 1] - arr[i] is not d, the answer is arr[i] + d.

class Solution {
    public int findMissing(int[] arr) {
        int n = arr.length;
        int d = (arr[n - 1] - arr[0]) / n;    // n gaps in the full row
        for (int i = 0; i + 1 < n; i++) {
            if (arr[i + 1] - arr[i] != d) return arr[i] + d;
        }
        return arr[0];                         // d == 0: every number is the same
    }
}

How long it takes: one walk, O(n). Extra room: O(1).

Way 2: the clever way

Every post before the gap stands exactly where it should: arr[i] == arr[0] + i * d. Every post after the gap is one step off. So "is post i in the right place?" is yes, yes, yes, then no, no, no. That is exactly what binary search is good at.

1. lo = 0, hi = n - 1. The last post is always off, so the first wrong post is somewhere in [lo, hi].
2. While lo < hi: look at mid. If arr[mid] is where it should be, the gap is after mid, so lo = mid + 1. Otherwise mid might be the first wrong post, so hi = mid.
3. When lo == hi, that is the first wrong post. The missing number is arr[0] + lo * d.

class Solution {
    public int findMissing(int[] arr) {
        int n = arr.length;
        int d = (arr[n - 1] - arr[0]) / n;
        if (d == 0) return arr[0];
        int lo = 0, hi = n - 1;                // the last post is always out of place
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == arr[0] + mid * d) {
                lo = mid + 1;                  // this post is fine: gap is to the right
            } else {
                hi = mid;                      // this post slid: gap is here or to the left
            }
        }
        return arr[0] + lo * d;                // where the first wrong post should be
    }
}

How long it takes: the range halves each time, O(log n). Extra room: O(1).

Watch out for

• Using hi = mid - 1 when the post is wrong. mid might be the first wrong post, so keep it with hi = mid.
• Overflow in arr[0] + mid * d when numbers are huge. Use long if the values can reach about a billion.
• A step of 0 (all numbers equal) has no gap. Return that number, as the code does.
• The problem promises the missing number is not at either end. Without that promise the answer is not even clear: [2, 4, 6] could be missing 0 or 8.

What interviewers ask next

• Find the missing number in 1..n (not sorted). Use the sum formula n(n + 1)/2 minus the sum, or XOR all values with 1..n.
• Sorted array of 0..n with one missing: the same binary search with arr[i] == i as the "in place" test.
• The k-th missing positive number in a sorted array. At index i, arr[i] - (i + 1) numbers are missing so far. Binary search on that count.
• Two numbers are missing from the AP. Walk once and find the two big gaps, or binary search twice with the count of missing ones so far.

Remember this

Grown-up words: the fence row is an arithmetic progression, the step is the common difference, and "yes, yes, then no, no" is a monotonic predicate that binary search finds in O(log n).