Missing Arithmetic number

Let $a_i$ be an element in the arithmetic progression, where $1 ≤ i ≤ n$ .

First find the common difference by calculating $\frac{a_n - a_1}{n-1} = \frac{a_1 + (n-1)d - a_1}{n - 1} = d$ , as the missing number cannot be $a_1$ or $a_n$ (otherwise there would be a shorter progression with no missing number). We can perform a binary search by splitting the progression into two, then calculating $\frac{a_{\lfloor n/2 \rfloor} - a_1}{d}$ and $\frac{a_{n} - a_{\lfloor n/2 \rfloor} }{d}$ . This will give us ${\lfloor n/2 \rfloor}-1$ , but if there are not this number of elements in the given range, it must contain the missing number.

Try this out with a list of 10 numbers in an arithmetic progression, say $1, 3, 5 \cdots 19$ to get a feel for this process. Now rinse and repeat until you find the missing number: and since a binary search has complexity $O(\log n)$ , the answer is $O(\log n)$ .

For the lazy: since this is multiple choice, use the process of elimination. The time complexity is at most $O(n)$ as we can find the missing element by calculating the successive differences (such as $a_2 - a_1, a_3 - a_2$ ). Hence we can rule out $O(n \log n)$ . The time complexity is definitely not $O(1)$ either as this task is more complex than finding a given number in a sorted list. Now you either have $O(n)$ or $O(\log n)$ , and it probably will be the least complex of the two choices.