Find the missing number using limited memory

Question

The problem is that for an input file with four billion unique integers, provide an algorithm for generating an integer that is not contained in the file, suppose it has only 10 MB of memory.

I searched for some solutions and published the code below, one of which is to store integers in blocks of a bit vector (each block representing a certain range of integers in the range of 4 billion, each bit in the block represents for an integer), and using a different counter for each block to count the number of integers in each block. Thus, if the number of integers is less than the block throughput for integers, scan the bit vector of the block to find the missing integers.

My question for this solution is: why "the closer to the middle we choose, the less memory will be used at any given time" , there is more context,

An array in the first pass can fit in 10 megabytes or about 2 ^ 23 bytes of memory. Since each element of the array is int, and int is 4 bytes, we can contain an array of no more than 2 ^ 21 elements. So, we can do the following:

Therefore, we can conclude the following: 2 ^ 10 <rangeSize <2 ^ 26, and these conditions give us a good amount of "room for maneuver", but the closer to the middle we choose, the less memory will be used at any given time.

public class QuestionB {
    public static int bitsize = 1048576; // 2^20 bits (2^17 bytes)
    public static int blockNum = 4096; // 2^12
    public static byte[] bitfield = new byte[bitsize/8];
    public static int[] blocks = new int[blockNum];

    public static void findOpenNumber() throws FileNotFoundException {
        int starting = -1;
        Scanner in = new Scanner (new FileReader ("Chapter 10/Question10_3/input_file_q10_3.txt"));
        while (in.hasNextInt()) {
            int n = in.nextInt();
            blocks[n / (bitfield.length * 8)]++;
        }

        for (int i = 0; i < blocks.length; i++) {
            if (blocks[i] < bitfield.length * 8){
                /* if value < 2^20, then at least 1 number is missing in
                 * that section. */
                starting = i * bitfield.length * 8;
                break;
            }
        }

        in = new Scanner(new FileReader("Chapter 10/Question10_3/input_file_q10_3.txt"));
        while (in.hasNextInt()) {
            int n = in.nextInt();
            /* If the number is inside the block that’s missing 
             * numbers, we record it */
            if (n >= starting && n < starting + bitfield.length * 8) {
                bitfield [(n-starting) / 8] |= 1 << ((n - starting) % 8);
            }
        }

        for (int i = 0 ; i < bitfield.length; i++) {
            for (int j = 0; j < 8; j++) {
                /* Retrieves the individual bits of each byte. When 0 bit 
                 * is found, finds the corresponding value. */
                if ((bitfield[i] & (1 << j)) == 0) {
                    System.out.println(i * 8 + j + starting);
                    return;
                }
            }
        }       
    }

    public static void main(String[] args) throws FileNotFoundException {
        findOpenNumber();
    }

}

Answer 1

M 2 ^ 32/M, - M + 2 ^ 27/M (32 ). , M = √2 ^ 27, 1 2 ^ 27 . 2 ^ 14,5 , 92 .

.

Answer 2

. , , , 100 . . , 100k, . , .