Before you read the answer here is a tip: the best answer sorts the file in linear time reading every number into memory only once.

Give up? Since the file contains all distinct integers between 0 and 10,000,000, we can use bits to represent whether every number in this range exists. For this we need only 10^7 bits or 1,250,000 bytes (1.25MB) so it can fit in memory. Here is some pseudocode:

boolean bit[10000000];

//An array of bits. I'm assuming a boolean array of size 8

// uses only one byte.

//Set it to 0

for (int i = i; i < n; i++){

bit[i] = 0;

}

//read every number from file

f = filestream("filename"); //pseudocode

while (int i << f){

bit[i] = 1;

};

//write it out

for (int i = i; i < n; i++){

if (bit[i] == 1)

cout << i;

};

This is a very old question. It appears in Programming Pearls by Jon Bentley, a really fun read!

## No comments:

Post a Comment