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 optimized away.
The above recursion is T(n) = T(n/2) + O(n), which solves to O(n), hence a solution for the problem.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: