Finding Missing Unsigned Integers in a 4‑Billion‑Element File Using Interval Counting and Bitmap Technique

The problem: given a file containing 4 billion unsigned 32‑bit integers (out of the full 0‑4,294,967,295 range), find every number that does not appear, using limited memory.

A naïve bitmap for the whole range would require about 500 MB (42,949,672,95 bits ≈ 5,368,791,1 B), which is too large.

The proposed solution splits the range into many intervals (e.g., 64 intervals). An integer array countArr[0..63] records how many numbers fall into each interval. After a single pass over the 4 billion numbers, any interval whose count is less than the expected size must contain missing values.

Because the array is only 64 × 4 B = 256 B, the memory usage is negligible.

For each under‑filled interval, a second pass is performed using a bitmap limited to that interval. For example, for interval 1 we allocate a bit array bitArr[0..67108863] (≈8 MB). While scanning the file again, we set bitArr[num - 2^26 * 1] to 1 for numbers belonging to this interval.

After the second pass, any bit still 0 corresponds to a missing number; its original value can be reconstructed as 2^26 * 1 + i, where i is the bit index.

In summary, the method combines interval counting with bitmap processing only on intervals that lack enough numbers, reducing the overall memory requirement from hundreds of megabytes to a few kilobytes.