CareerCup 12.3

Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory.
FOLLOW UP
What if you have only 10MB of memory?

Integers have range from -2^31 to 2^31 and so they can be mapped into a 2^32 bits map.
And with 1GB we can have a 2^38 bits map. It can be done in 2 pass processing So O(n).

I didn't finish the followup though and just found a solution from some other websites.

The idea is that a sequence of bits can do not only mapping but also counting. It only needs 32 bits for counting upto 2^32. That is the power of permutation.
So we can divide those integers into blocks of 1024 and set a counter for each block. For example, 515 is between 1~1000, so counter[0]++.
Doing like this, we need 2^32/2^10= 2^22 blocks. and 10 bits for per block. Totally it needs 2^22*10 < 10MB.
After counting thru the integers, we look for any range whose counter is less than 1000.
Now it's sure that there's a gap in the range and it's trivial to get it with 10MB memory.

The only doubt I have is what if all counters are over 1000. I guess it's not gonna happen because 4 billion < 2^32.