@Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing.....
On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu <duman...@gmail.com> wrote: > 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 <radhakrishnance...@gmail.com> > 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 <duman...@gmail.com> 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 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. > > -- > 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. > > -- 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.
