CareerCup

I'll solve a simplified version of the problem. You should be able to extend it to solve your problem.

You have a large number of integers between 1 to 100000 in a file. However, you can only store a single array of length. How do you find an integer on in that file.

1. Divide the range of integers to 10. Meaning 1 - 10000 maps to index 1 in the array, 10001 - 20000 maps to 2 etc
2. Read each integer from the file and find out its corresponding index in the array as described in 1. And increment the value at that array by 1.
3. After you are done reading. Find the index of the array that has the least value. There must be some element in the array, whose value is less that 10000. (If not, all possible integers are on the disk.)
4. Now you know the range where you can find a missing integer. Lets say, it is between 50001 to 60000.
5. Set all the array indices to 0. Now index 1 in the array corresponds to 50001 to 51000, index 2 maps to 51001 to 52000 and so on
6. read the file again and find out the array index with the smallest value
7.  ...
8. ...

Hope you get the idea. Sorry about the horrible pseudocode!

Sum the every thing and subtract it from the sum for first billion+1 integers , you have your missing number.

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

Now first of all you must note something even though it says 10billion you can have only 4billion distinct integers (2^32). S if we had 500MBmemory we could have mapped each of these integers to a bit vector.

Since we have less memory vijay's solution should be used.

As a last note this is actually a question from the book and both of these solutions are discussed in depth.

Are those integers supposed to be continuous? If yes, you need only O(1) memory and O(N) complexcity. The algo is:

1. Sum all the integers from the given array and store it as A.
2. Calculate the expected number via this equation: B = (min + max) * number / 2;
3. The missing number is B - A