@ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji <[email protected]>wrote:
> @ankit: pls explain the time complexity.. > i dont think its O(log n) > > > On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal <[email protected]>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 <[email protected]> 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 <[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. >> > >> > >> >> -- >> 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. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- 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.
