Archives
Categories
Advertisements
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.
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
The above recursion is , which solves to
, hence a solution for the problem.