Suppose you have a 2^40 integers(4-byte-sized each) in a file, and you have a limited 15M physical memory, write a program to output an integer(4-byte

Suppose you have a 2^40 integers(4-byte-sized each) in a file, and you have a limited 15M physical memory, write a program to output an integer(4-byte-sized) that is not in the file, or report out there is no such integer.

Make a bit vector 15M=15*2^20*8=120*2^20 bit, then traverse the file, set corresponding bit when u hit a integer and that bit is unset, first time the check range is 0~120*2^20-1, if the there is one bit is unset, that integer corresponding to that bit is missing. The maximum iteration is 2^32/120*2^20=35 (the file is sorted and each iteration, should fill in all bit vector)