Return to Answer

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

###Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

###Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

###Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

###Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

###Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

###Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

###Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

###Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

###Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...