Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity <O(n) we have to scan the file at least once
Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit && right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu <[email protected]> wrote: > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
