Treat the 2 megabytes of RAM as 1 million short integers (16 bits).
Read through the file and count the number of occurrences of the SSNs
divided by 1000, i.e., the first 6 digits of each number. If the
numbers are distinct, there can't be more than 1000 in each bin, so
you can cap the counters at 1000 and not have to worry about
overflows; something like (if k is the SSN):
a[k/1000] = a[k/1000] < 1000 ? a[k/1000] + 1 : 1000;
Any a[i] that is less than 1000 gives the first 6 digits of a missing
number. Now use the 2 megabytes of RAM as an array of 1000 flags, and
go back through the file and select the numbers with those first 6
digits, and set the flags corresponding to the last three digits. Any
unflagged number gives the last 3 digits of a missing number. Combine
the first 6 and the last 3 digits to get the entire missing number.
Dave
On Feb 7, 4:03 am, snehal jain <[email protected]> wrote:
> given file containing roughly 300 million social security nos. ( 9
> digit nos.) find a 9 digit no. that is not in the file. you have
> unlimited drive space but only 2 megabytes of RAM at your disposal.
--
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.
