Gene wrote:
I'm sorry, but the response below is wrong on several levels. See
notes.
C Erler wrote:
Because there are infinite integers, there is no need for a list of
4,300,000,000 of them to contain a duplicate. If there are
4,299,999,999 choices, there will be one duplicate.
Terry wrote:
This problem is from the book programming pearls . Can anyone explain
me the soln. How does he do it.
Given a file containing 4,300,000,000 integers, how
can you find one that appears at least twice? (Explain, first,
why this must happen.)
Binary search finds an element
Terry wrote:
Gene wrote:
I'm sorry, but the response below is wrong on several levels. See
notes.
C Erler wrote:
Because there are infinite integers, there is no need for a list of
4,300,000,000 of them to contain a duplicate. If there are
4,299,999,999 choices, there will be
Because there are infinite integers, there is no need for a list of
4,300,000,000 of them to contain a duplicate. If there are
4,299,999,999 choices, there will be one duplicate. Because the
solution uses binary search, the list is sorted.
So, the full problem is probably something like the
