@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 <anand.shastr...@gmail.com> 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 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.
