here is my approach : STEP 1: 300 million integers take 300*10^6*4 bytes of memory, but we have only 2 MB RAM which 2*10^6. By dividing these, we get that we need to break the file containing sequence of 300 million numbers into around 600 files. Divide the bigger file into 600 smaller files.
STEP 2: Now take each file into memory one by one and min heapify them and put them back in the memory. Now the first element of each file will be the minimum element of each file and so on. STEP 3: Now take the first element from each file into the memory. After taking element from each file, remove that element and again min heapify the sequence of numbers in that file. STEP 4: Min Heapify the list of numbers in memory and remove the minimum element. STEP 5: Take another element from the file of which the element in step 4 was removed and again min heapify both of them. Time complexity : O(long n), where n is the total no. of numbers Continue this process till u find a no. which is missing in the sequence... I hope this algo is clear... Ankit Sambyal On Thu, Jun 9, 2011 at 4:46 AM, 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.
