@Atul: Here is one way to do it: Treat the array as a million 16-bit integers: short a[1000000].
Set the array to zero. Read through the file, and for each number k, increment a[k%1000000]. Since the numbers are distinct, there can be at most 900 numbers in each bin. Find j such that a[j] < 900. You now know that there is a missing number with the six-digit number j as the final six digits. Set a[100] to a[999] to zero. Read through the array again. Ignore any number k whose last six digits are not j. For the remaining numbers, set a[k/1000000] = 1. Find i, with 100 <= i <= 999, such that a[i]==0. This gives you the first three digits of a missing number. Put the first thee digits together with the last six digits: k = 1000000*i + j to get a number that is not in the file. Dave On Jun 23, 7:59 am, atul purohit <[email protected]> wrote: > Hi, > > Can someone explain me how to do this. > > Given a file containing roughly 300 million 9-digit numbers. Find a 9-digit > number that isn't present in the file.You have unlimited drive space but > only 2MB of RAM available. > > I suppose we have to use bit-vectors n all but still couldnt figure out a > proper way. A few steps or an algo will be great. > > Cheers, > Atul -- 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.
