few problems, approaches and solutions

## Problem 4-2

### Problem:

Given, an array of size $n$ with distinct elements such that $0 <= A[i] <= n$ for each element $i$. 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.

```/* partition array with elements, according to b bit of each
element and return the partition index. */
int partition(int * arr, int n, int b)
{
int i, part=0;

/* invar: part points to the first set bit seen so far. */
for (i=0;i<n;i++) {
if(!bit_access(arr, i, b)) {
swapa(arr, i, part);
part++;
}
}

return part;
}

int find_misng_rec(int *arr, int n, int num, int bits)
{
int part;

if (n==0) return num;

part = partition(arr, n, bits);

if (part < 1<<bits)
return find_misng_rec(arr, part, num<<1, bits-1);
return find_misng_rec(arr+part, n-part, (num<<1)+1, bits-1);
}
```

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.