Programmingpearl

Waiting for solved

  • given a large number of integers (4 billion input), find the missing number if we only have a few hundred bytes of main memory and several spare sequential files. (hint: binary search)

my thinking:

use bit map to sort them and scan to find missing integer. But it need ample memory.

Solution:

while get the input from the file
    m = middle of the range
    if num < m 
         output file1
     else output file2
 if file1 has more number
     repeat process with file2
 else repeat process with file1
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License