Answer to Question #294914 in C++ for Abhik

Question

Let n = 2^l − 1 l for some positive integer l. Suppose someone claims to hold an unsorted array A[1 · · · n] of distinct l-bit strings; thus, exactly one l-bit string does not appear in A. Suppose further that the only way we can access A is by calling the function

FETCHBIT(i, j), which returns the jth bit of the string A[i] in O(1) time. Describe an algorithm to find the missing string in A using only O(n) calls to FETCHBIT. Again, give either pseucode or write a generic description.

Demonstrating the algorithm on a specific example will not fetch any marks.

Answer 1

This convention is to call the least significant bit as 0-th bit. The number of digits required to represent

n is at least log (n + 1)e. The most significant bit of n is the (log (n + 1)e − 1)-th bit of it.

In the integers between 0 to n, exactly 2(log(n+1)e−1) numbers are < 2

(log (n+1)e−1). Considering that (log (n + 1)e − 1)-th bit of any non-negative number ≤ n we can determine whether the number is

< 2

(log (n+1)e−1). We now look at the (log (n + 1)e − 1)-th bit of all the numbers in A[1...n]. Populate two

lists of references (e.g. pointer, index, handle, etc) during the first n lookup. Reference to the numbers

with 0 in their (log(n + 1)e 1)-th bit are kept in one, while the others are kept in the other.The size of the first list is the

count of numbers < 2

(log (n+1)e−1). The missing integer is < 2

(log (n+1)e−1) iff this count is 2(log(n+1)e−1) − 1.

In that case, we look for the missing integer in the first list. Otherwise, we look at the second list. In this

In this process, we figure out the (log (n + 1)e − 1)-th bit of the missing integer in n bit lookup.

We want to use recursion to search for the appropriate list. The fact that we now search for a list of references

As an example, to convert to numbers rather than a list of numbers, you can do so as follows: The initial problem comes with the list of

all the references. The fact that the search range could be shifted in the subproblem is handled by replacing

all of the (log(n + 1)e 1)-th bits are set to 0.However, as we never read the (log (n + 1)e − 1)-th bits again, we don’t

have to make this modification explicitly.