Total possible 9 digit numbers = 10^9 < 2^32 We have = 3 X 10^8 numbers < 2^32
notice that if we observe only 16 msb of social security numbers, we will have atleast one combination (of the 16 most significant bits) which will occur less that 2^16 times. 1. Now with this, we build an array A of 2^16 integers (indexed on the 16 msb) in RAM, initialized to 0. (2^16 X 4 bytes = 256 KB) 2. Scan the hard disk containing social security numbers. for each social sec number X, do A[X>>16] ++ 3. now find out i such that A[i] < 2^16. Call this as M = i 4. Now we know that for the 16 msb of M we have atleast one combination of 16 lsb such that the number is absent. 5. build a bit array B of size 2^16, initlialized to 0 6. rescan the hard disk and whenever you find an X such that X>>16 = M, do B[(X<<16)>>16] = 1 7. Now scan the bitarray B to find i such that B[i] = 0. Call this as N = i; Q = N bitwise or M is one missing element. Done in 2 scans. On Sat, Oct 29, 2011 at 11:46 PM, Arun Vishwanathan <aaron.nar...@gmail.com>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 <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. > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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.
