@ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal <ankitsamb...@gmail.com>wrote:
> Lets say we have 9 numbers from 1 to 10 and one number is missing. We > hv a RAM which can accomodate only 3 nos. > 9,6,7,4,3,2,1,5,10 > So, we split the file into 3 smaller files each containing 3 nos. > File1: 9,6,7 > File2: 4,3,2 > File3: 1,5,10 > > Now take each file into memory one by one and min heapify > them and put them back in the memory. > File1: 6,9,7 > File2: 2,3,4 > File3: 1,5,10 > The 1st element in each file is min in each file. > > Now make a file temp containing the 1st element of each file and > remove the 1st element from the files 1,2 and 3.Min heapify each > file.. > Temp: 1,6,2 > File1: 7,9 > File2: 3,4 > File3: 5,10 > > Now remove 1 from file Temp and take element from File3 because 1 > belonged to File3 originally. Again min Heapify them. > Temp: 2,6,5 > File1: 7,9 > File2: 3,4 > File3: 10 > > Now remove 2 > Temp: 3,5,6 > File1: 7,9 > File2: 4 > File3: 10 > > Now remove 3 > Temp: 4,6,5 > File1: 7,9 > File2: > File3: 10 > > Now going on this way we will find that after we remove 7, we could > not find 8. So, 8 is the missing no. > > > Ankit Sambyal > BITS Pilani > > > > On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa <varunpahwa2...@gmail.com> > wrote: > > can anyone explain "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." in dumanshu's solution. > > > > On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa <varunpahwa2...@gmail.com> > > wrote: > >> > >> @ankit :please explain by taking an example. > >> > >> On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji <vetribal...@gmail.com> > >> 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 <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. > >> > >> > >> > >> -- > >> Varun Pahwa > >> B.Tech (IT) > >> 7th Sem. > >> Indian Institute of Information Technology Allahabad. > >> Ph : 09793899112 ,08011820777 > >> Official Email :: rit2008...@iiita.ac.in > >> Another Email :: varunpahwa.ii...@gmail.com > >> > >> People who fail to plan are those who plan to fail. > >> > > > > > > > > -- > > Varun Pahwa > > B.Tech (IT) > > 7th Sem. > > Indian Institute of Information Technology Allahabad. > > Ph : 09793899112 ,08011820777 > > Official Email :: rit2008...@iiita.ac.in > > Another Email :: varunpahwa.ii...@gmail.com > > > > 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 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.
