Find an integer not in the list of 4 billion using 4 mb. But 4 MB is not enough

Question

Given a list of 4 billion integers, find an integer not on the list using 4 MB of memory. (the interview was in Java)

My solution is to use BitSet.

However, according to my calculations, there is not enough bits in 4 MB of memory! = C

4 megabytes = 4096 KB # times 8

4096 KB = ~ 4096000 bytes # multiply by 1000

4,096,000 Bytes = ~ 33,500,000 bits # multiply by 8

Thus, 33.5 million bits are two orders of magnitude less than a billion. Let one billion.

---

Or is this part of the question for dealing with this limitation?

Answer 1

This question does not say that you can only do one data pass.

So, assuming this is not an error, you can still use a bit, but do it in groups. For the first pass, check only the numbers from zero to thirty million (approximately). Second pass, check thirty to sixty million. And so on.

This will still allow you to find the missing number within the limits of the question.

Answer 2

You need a color filter .

Unlike a standard hash table, a fixed size Bloom filter can represent a set with an arbitrary large number of elements; adding an element never fails due to the fact that the data structure is "populated". However, the false positive rate steadily increases as elements are added until all bits in the filter are set to 1, after which all requests give a positive result.

Some additional reading

Answer 3

iterate through the list and save the maximum number. then int notInList = max + 1