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.
