@Arun: If, for example, you find that a[54321] < 10000, you know that there is an available number with those low order digits. Then you look through the numbers with those low order digits to find an unused set of high order digits. If, for example, on the second pass you find that a[9876] is >= 0, that means that you didn't find the number 987654321 in the file, because if you had found it you would have set a[9876] to -1.
Dave On Oct 29, 1:16 pm, Arun Vishwanathan <[email protected]> wrote: > can someone give me a short explanation of Dave solution? I understand that > a[n%100000] < 10000 is trying to find the bin which has less than what > maximum numbers it can hold and the bin is such that all numbers counted in > this have the same remainder when divided by 100000. I do not get the > a[n/100000] part after that ..wat is that trying to say? > > > > > > On Sat, Oct 29, 2011 at 10:42 AM, yq Zhang <[email protected]> wrote: > > 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. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- 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.
