Find any one of multiple possible repeated integers in a list

user_661284 0
Viewed 2735

Given an array of n+1 integers, each in the range 1 to n, find an integer that is repeated.

I was asked this at a job interview. Here's my answer: The Pigeonhole Principle says there has to be a repeat. I tried to use a binary search approach, so I did this in Matlab, because that's what I know:

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

So then I argue that one of these, top or bot, has to be bigger than n/2 by the PhP again. Take that range and repeat.

I thought this was a pretty good solution, but the interviewer sort of hinted that one can do better. Please post any better solutions you know of.

duplicates search algorithm
6 Answers

We use circle detection's idea to solve this problem.

All we need to do is first find the begin of the circle and then find the duplicated one in the circle.

Here's the code in c++:

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];

    while(slow != fast){
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}
user_74244780
Related