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 <zhangyunq...@gmail.com> 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 <bagana.bharatku...@gmail.com>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 <dave_and_da...@juno.com> 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" <shiv.jays...@gmail.com> 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 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. >>> >>> >> -- >> 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. >> > > -- > 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. > -- "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 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.
