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 following. There is a sorted list of the first 4,299,999,999 positive integers. Someone duplicates one of them and inserts it into the list right next to the original. Figure out which integer is duplicated. With that, it is easy to solve. If you look at the first 5000 integers, the last one should be 5000. If the last one is 4999, you know that the duplicate is in that sublist. So, basically, you take the first half or so of the list and see if the last one is too low. That will tell you which half of the list has the duplicate. Repeat until your sublist has only the duplicated entry. --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
