Find the missing integer

Given a tape that contains at most 1,000,000 twenty-bit 
integers in random order, find a twenty-bit integer that isn't 
on the tape (and there must be at least one missing - Why?).
  a. How would you solve this problem with ample quantities of 
main memory? 
  b. How would you solve it if you had two tape drives, but
only a few dozen words of main memory?
  c. How would you solve it with only one tape drive (which contains 
the input), and only 48 words of main memory?


Solution:

  Here's the discussion + solution in Bentley's "Programming Pearls"

  [a.] Given a tape that contains at most one million twenty-bit integers 
in random order, we are to find one twenty-bit integer not on the tape. 
(There must be at least one missing, because there are 2^20 or 1,048,576 
such integers.) With ample main memory, we could use the bit-vector technique 
[...] and dedicate 131,072 8bit bytes to a bitmap representing the integers 
seen so far. 
  
  [b.] The problem, however, also asks how we can find the missing integer if 
we have only a few dozen words of main memory and several extra tape 
drives. To set this up as a binary search we have to define a range, a 
representation for the elements within the range, and a probing method to 
determine which half of a range holds the missing integer. How can we do this? 
We'll use as the range a sequence of integers known to contain at 
least one missing element, and we'll represent the range by a tape containing 
all the integers in it. The insight is that we can probe a range by counting 
the elements above and below its midpoint: either the upper or the lower 
range has at most half the elements in the total range. Because the total range 
has a missing element, the lesser half must also have a missing element. 
These are most of the ingredients of a binary search algorithm for the problem; 
try putting them together yourself before you peek at the solutions to see 
how Ed Reingold did it. These uses of binary search just scratch the surface 
of its applications in programming. A root finder uses binary search to solve 
a single-variable equation by successively halving an interval; numerical 
analysts call this the bisection method. When the selection algorithm in 
Solution 10.9 partitions around a random element and then calls itself 
recursively on all elements on one side of that element, it is using a 
"randomized" binary search. Other uses of binary search include tree data 
structures, data processing algorithms that run on card sorters (which use 
the corresponding decimal search), and program debugging (when a program dies 
a silent death, where do you place print commands to home in on the guilty 
statement?). In each of these examples, thinking of the program as a few 
embellishments on top of the basic binary search algorithm can give the 
programmer that all-powerful aha! 

  [Ed Reingold's solution of b. -- book, page 165]:

  It is helpful to view this binary search in terms of the twenty bits 
that represent each integer. In the first pass of the algorithm we read the 
(at most) one million input integers and write those with a leading zero bit 
to one tape and those with a leading one bit to another tape. One Probe \ One 
of those two tapes contains at most 500,000 integers, so we next use that tape 
as the current input and repeat the probe process, but this time on the second 
bit. If the original input tape contains N elements, the first pass will read N 
integers, the second pass at most N/2, the third pass at most N/4, and so on, 
so the total running time is proportional to N. The missing integer could be 
found by sorting on tape and then scanning, but that would require time 
proportional to N log N. This problem and solution are due to Ed Reingold of 
the University of Illinois.
  

  c. Here is an elegant, randomized solution. In our 48 8-words
of main memory, we have enough space to store 16 randomly, independently
generated 20-bit words, sorted in increasing order (we only need a 
negligible time to sort these words).
  In the remaining 48*8-16*20 = 64 bits we can keep a 1-bit marker 
(initially 0) for the index of each random word (so we need 16 more bits).
  Pass once through the tape. For each word we read, we check if it 
is already among our randomly generated words. (For this, we just 
make a binary search in a 16-long sorted list - at most 5 comparisons).
If we found that a word in memory is on the tape, we mark it, by making 
its bit equal to 1 (so, we do at most one write operation per tape word).
  After the pass, we check to see if there is a word among the 16 ones
in memory, that was not found on the tape, by checking all the bits.
If all bits are marked, we repeat. Otherwise, output one word whose
corresponding bit is 0.
  Let's compute now the probability that all the 16 random words are 
on the tape.

   Pr(x1, x2, ..., x16 are all on the tape) = 

 = Pr(x1 is on the tape)*P(x2 is on the tape)*...*P(x16 is on the tape)

 = Pr(x1 is on the tape) ^ 16     (since the words are independently, 
                                   identically distributed - obviously 
                                   uniform in the 20-bit word space)

 <= ( 10^6 / 2^20 )^16 = (5^6 / 2^14)^16 = (5^3/2^7)^32 ~ 0.468

  So, the probability of success is more than 50%. Since the number of 
passes is geometrically distributed, the expected number of passes is then
at most 2.