@Dave awesome..! On Sat, Jul 16, 2011 at 7:15 PM, Dave <[email protected]> wrote:
> @Anand: Assuming that the file contains unsigned 32-bit integers. Set > an integer array a[65536] to zero, read through the file and tally the > numbers based on their low-order 16 bits: a[j&0xFFFF]++. Since 4.3 > billion exceeds 2^32, by the pigeonhole principle, there will be at > least one tally, say a[k], that has a value greater than 65536. Set > the array to zero again. Read through the file again. Ignore all of > the numbers whose low-order 16 bits are not k, and tally numbers based > on their upper 16 bits: a[(j>>16)&0xFFFF]++. Again by the pigeonhole > principle, there will be at least one number that exceeds 1. Now you > know the high-order 16 bits and the low-order 16 bits of a number that > occurs at least twice. You can quit the second pass as soon as you > have your first tally equalling 2. > > Dave > > On Jul 15, 8:28 pm, Anand Shastri <[email protected]> wrote: > > Given a file containing 4,300,000,000 integers, how > > can you *find **one* that *appears* at *least **twice* > > -- > 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.
