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.
