Given the SSN number is 9 digit number, the total space of possible numbers are 1000million. So I think Dave's solution works.
On Sat, Oct 29, 2011 at 8:47 AM, bharat b <[email protected]>wrote: > @Dave > Your solution works if the total no.of records(ssn numbers) is 1000 > million. > But the question states that there are only 300 million numbers. > > I think some modification is needed to your answer. > Correct me if i am wrong. > > > > On Fri, Oct 28, 2011 at 2:04 AM, Dave <[email protected]> wrote: > >> @Shiva: Using an integer array a[100000], initialized to 0, read >> through the file and for each number n, increment a[n%100000]. At the >> end of the file, find any k such that a[k] != 10000. Then read through >> the file again. For any number n such that n%100000 == k, set a[n/ >> 100000] = -1. At the end of file, find any j < 10000 such that a[j] >= >> 0. Then 100000 * j + k is a number that is missing from the file. >> >> Dave >> >> On Oct 27, 10:25 am, "shiva@Algo" <[email protected]> wrote: >> > Given a file containing roughly 300 million social security >> > numbers(9-digit numbers), find a 9-digit number that is not in the file. >> > You have unlimited drive space but only 2megabytes 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. >> >> > -- > 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.
