hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check "u are going to check whether a number N exist ".
On Jun 9, 4:46 pm, radha krishnan <[email protected]> wrote: > 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.
