Lin Ma - 1 year ago 53

C++ Question

I am debugging below problem and post the solution I am debugging and working on, the solution or similar is posted on a couple of forums, but I think the solution has a bug when num[0] = 0 or in general num[x] = x? Am I correct? Please feel free to correct me if I am wrong.

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).

You must use only constant, O(1) extra space.

Your runtime complexity should be less than O(n2).

There is only one duplicate number in the array, but it could be repeated more than once.

`int findDuplicate3(vector<int>& nums)`

{

if (nums.size() > 1)

{

int slow = nums[0];

int fast = nums[nums[0]];

while (slow != fast)

{

slow = nums[slow];

fast = nums[nums[fast]];

}

fast = 0;

while (fast != slow)

{

fast = nums[fast];

slow = nums[slow];

}

return slow;

}

return -1;

}

Answer Source

- Start with two pointers to the first element:
*fast*and*slow*. - Define a 'move' as incrementing
*fast*by 2 step(positions) and*slow*by 1. - After each
*move*, check if*slow*&*fast*point to the same node. - If there is a loop, at some point they will. This is because after they are both in the loop,
*fast*is moving twice as quickly as*slow*and will eventually 'run into' it. - Say they meet after
*k moves*. This is NOT NECESSARILY the repeated element, since it might not be the first element of the loop reached from outside the loop.

Call this element*X*. - Notice that
*fast*has stepped*2k*times, and*slow*has stepped*k*times. - Move
*fast*back to zero. - Repeatedly advance
*fast*and*slow*by ONE STEP EACH, comparing after each step. - Notice that after another
*k*steps, slow will have moved a total of*2k*steps and*fast*a total of*k*steps from the start, so they will again both be pointing to*X*. - Notice that if the prior step is on the loop for both of them, they were both pointing to
*X-1*. If the prior step was only on the loop for*slow*, then they were pointing to different elements. - Ditto for
*X-2, X-3,*... - So in going forward, the first time they are pointing to the same element is the first element of the cycle reached from outside the cycle, which is the repeated element you're looking for.