Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM.
Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
