Problem 4-2

Problem:

Given, an array of size with distinct elements such that for each element . Note that the array should be missing an integer from range [], as the array has size and the range has elements. The only way to access elements is through function

bit_access(int * A, int i, int j)

which returns the bit of element in array .

We have to find out the missing number in time.

Approach:

Let bit be the most significant set bit of n. What we observe is that the elements of could be divided into two sets, based on the bit of those elements. Those which have the bit set, and those which don’t. We know that number of elements with bit 0 should be . 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 bit as 0, otherwise its 1. The algorithm works on this observation by first partitioning the array according to 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 , which solves to , hence a solution for the problem.

~ by ciju on June 2, 2008.