CLRS (Page 85): Problems 4-2 : Finding the missing integer

Problem:

An array A[1...n] contains all the integers from 0 to n except one. It would be easy to determine the missing

integer in O(n) time by using an auxiliary array B[0...n] to record which numbers appear in A. In this
problem, however, we cannot access an entire integer in A with a single operation. The elements of A are
represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i],” which
takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n) time.

Solution:

Our convention is to call the least significant bit (LSB) as 0-th bit. Number of digits required to represent
n is at least dlg(n + 1)e. Most significant bit (MSB) of n is the (dlg(n + 1)e − 1)-th bit of it.
Among the integers between 0 to n, exactly 2
(dlg(n+1)e−1)
numbers are < 2
(dlg(n+1)e−1)
. If we look at
the (dlg(n + 1)e − 1)-th bit of any non-negative number ≤ n we can determine whether the number is
< 2
(dlg(n+1)e−1)
. We now look at the (dlg(n + 1)e − 1)-th bit of all the numbers in A[1...n]. We populate two
lists of references (e.g. pointer, index, handle etc) during the first n lookup. Reference to the numbers having
0 in their (dlg(n + 1)e − 1)-th bit are kept in one and the rest in the other. The size of the first list is the
count of numbers < 2
(dlg(n+1)e−1)
. The missing integer is < 2
(dlg(n+1)e−1)
iff this count is 2
(dlg(n+1)e−1) − 1.
We look for the missing integer in the first list in that case. Otherwise, we look in the second list. In this
process, we figure out the (dlg(n + 1)e − 1)-th bit of the missing integer in n bit lookup.
We want to use recursion to search the appropriate list. The fact that now we search in a list of references
to numbers in stead of a list of numbers can be handled as follows. The initial problem comes with the list
all the references. The fact that the search range could be shifted in the subproblem is handled by replacing
all the (dlg(n + 1)e − 1)-th bits as 0. However, as we never read the (dlg(n + 1)e − 1)-th bits again we don’t
have to do this modification explicitly.



find_missing_integer ( list_of_references, n )
if ( n is 1 )
print 0-th bit of missing number is (1 - the number in the list)
return
left_list . initialize ()
right_list . initialize ()
msb_position <- ceiling( lg(n+1) ) - 1
forall number in list_of_references
if ( number [ msb_position ] is 0 )
left_list . insert ( number )
else
right_list . insert ( number )
if ( left_list . size () < power_of_two ( msb_position ) )
print msb_position-th bit of missing number is 0
find_missing_integer ( left_list, power_of_two ( msb_position ) - 1 )
else
print msb_position-th bit of missing number is 1
find_missing_integer ( right_list, n - power_of_two ( msb_position ) )


Complexity: O(log n)
Code: