Assuming the data is 32-bit unsigned integers: Treat your memory (either amount) as an array A[] of M integers. E.g., with 10 MB of memory, M = 2,500,000. Initialize the array to zero. Read through the file. For each integer x, increment A[x mod M]. There will be at least one bin whose count is no more than 4,000,000,000 / M = 1,600. Call it bin i. Let K = maximum_unsigned_integer / M. This is the number of possible integers mapping to each bin. E.g., with 10 MB of memory, K = 1717. There must be at least one unused integer in bin i. Clear the first K elements of A[]. Read through the file. For each integer x, if x mod M = i then set A[x/ M] = 1. Now find j such that A[j] is zero. Then the integer j * M + i is missing from the file.
The above algorithm is suitable as long as M >= sqrt(maximum_unsigned_integer). Dave On Mar 16, 4:18 pm, bittu <shashank7andr...@gmail.com> wrote: > Given an input file with four billion integers, provide an algorithm > to generate an integer which is not contained in the file. Assume you > have 1 GB of memory. > > 2nd Part > What if you have only 10 MB of memory? > > Thank > Shashank -- 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.
