Problem 4-2

###Problem:###

Given, an array of size $n$ with distinct elements such that for each element $i, 0\leq A[i] \leq n$. Note that the array should be missing an integer from range [$0,n$], as the array has size $n$ and the range has $n+1$ elements. The only way to access elements is through function bit_access(int * A, int i, int j) which returns the $j^{th}$ bit of element $i$ in array $A$.

We have to find out the missing number in $O(n)$ time.

Approach:

Let $b^{th}$ bit be the most significant set bit of n. What we observe is that the elements of $A$ could be divided into two sets, based on the $b^{th}$ bit of those elements. Those which have the bit set, and those which don’t. We know that number of elements with $b^{th}$ bit 0 should be $2^{b-1}$. And the remaining elements would have the bit set. If the number of 0’s doesn’t match the expected count, then the missing element has its $b^{th}$ bit as 0, otherwise its 1. The algorithm works on this observation by first partitioning the array according to $b^{th}$ bit and then applying the same logic recursively on the sub-array which has the element missing from the range.

Here’s the code for partition and recursive search of solution.

Tail recursion is optimized away. The above recursion is $T(n) = T(n/2) + O(n)$, which solves to $O(n)$, hence a solution for the problem.