@ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal <ankitsamb...@gmail.com>wrote:
> @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. > > -- 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.
