9

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;
}
Improve this question
18
  • 1
    now I understood what you meant to say.I think for this problem where nums[i]==i then you must start from any other point.You can have one outer loop where it check where nums[i]!=i and then you can proceed from that position.Do you think this may also break? Commented Oct 19, 2015 at 5:48
  • 1
    if i!=0 then it will not cause a problem because slow pointer will stuck at that position and fast will eventually reach the same position and while loop will break and in second while loop when slow is still stuck fast will reach there and find the duplicate.But when nums[0] = 0 then you need to handle that case separately.ex:int nums[] = {4,1,3,2,2} here arr[1]==1 but this will not cause a problem,you can easily figure it out using pen and paper. Commented Oct 19, 2015 at 6:05
  • 2
    This allgorithm basically doesn't work, and x[i]=i is the lesser of its problem. The bigger problem is that it will never see the duplicate in [1,2,3,0,4,4]. Commented Oct 19, 2015 at 6:08
  • 1
    There are two possibilities when arr[i] == i that are either arr[i] is a duplicate then there is no problem, above algorithm will work fine.And 2nd possibility is that arr[i] == i and arr[i] is not a duplicate (say i is non zero,we can handle that case separately ), then my claim is that you will never reach at position i by above algorithm.If you feel anything wrong in that then please provide and counter example.(Once again i==0 case is handled separately) as I don't know how to say it formally. Commented Oct 19, 2015 at 6:16
  • 3
    @Khatri There seems to be an internal contradiction in the question, it says x[0]==0 is a problem, so I take 0 is permitted. If it's not then the algorithm is probably OK. Commented Oct 19, 2015 at 9:23

4 Answers 4

Reset to default
8

Below is my code which uses Floyd's cycle-finding algorithm:

#include <iostream>
#include <vector>
using namespace std;

int findDup(vector<int>&arr){
    int len = arr.size();
    if(len>1){
        int slow = arr[0];
        int fast = arr[arr[0]];
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[arr[fast]];
        }
        fast = 0;
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
    return -1;
}

int main() {
    vector<int>v = {1,2,2,3,4};
    cout<<findDup(v)<<endl;
    return 0;
}

Comment This works because zeroes aren't allowed, so the first element of the array isn't part of a cycle, and so the first element of the first cycle we find is referred to both outside and inside the cycle. If zeroes were allowed, this would fail if arr[0] were on a cycle. E.g., [0,1,1].

Improve this answer
Sign up to request clarification or add additional context in comments.

22 Comments

your while will return false on the first iteration
I don't understand why that is a problem?
Here is one very nice explanation of above algorithm.link This algorithm is called Floyd's cycle-finding algorithm and uses concept of rho shape, you can read in the link for more details.
Your fast = arr[0] (line 9) should be fast = arr[arr[0]].
This works because zeroes aren't allowed, so the first element of the array isn't part of a cycle, and so the first element of the first cycle we find is referred to both outside and inside the cycle. If zeroes were allowed, this would fail if arr[0] were on a cycle. E.g., [0,1,1].
|
3

The sum of integers from 1 to N = (N * (N + 1)) / 2. You can use this to find the duplicate -- sum the integers in the array, then subtract the above formula from the sum. That's the duplicate.

Update: The above solution is based on the (possibly invalid) assumption that the input array consists of the values from 1 to N plus a single duplicate.

Improve this answer

6 Comments

Very smart, keithmo, but how do you prove there is duplicate?
"There is only one duplicate number in the array, but it could be repeated more than once." But the idea is great.
Oops, I missed the "...repeated more than once" part. My bad.
Hi keithmo, I think you are correct, there is only one duplicate number. The problem itself has issues.
I suppose the problem as described would allow, for example, N = 5 and the array = [1, 1, 5, 1, 1, 2]. If so then my solution would fail badly.
|
1
  1. Start with two pointers to the first element: fast and slow.
  2. Define a 'move' as incrementing fast by 2 step(positions) and slow by 1.
  3. After each move, check if slow & fast point to the same node.
  4. 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.
  5. 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.
  6. Notice that fast has stepped 2k times, and slow has stepped k times.
  7. Move fast back to zero.
  8. Repeatedly advance fast and slow by ONE STEP EACH, comparing after each step.
  9. 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.
  10. 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.
  11. Ditto for X-2, X-3, ...
  12. 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.
Improve this answer

12 Comments

And let me add that this is just an explanation of @Khatri's algorithm, which is good, and that you should accept his answer and not mine.
Thanks Dave, I read your comments again above and did some exercise, I think my understanding, "when there is a circle, there must be two elements in the array pointing to the entry point of circle, and faster/slower runner met at entry point of circle (in your algorithm), and it is why the index of array of begin circle is the duplicate elements, correct? ", is exactly what you mean? If I am wrong, please feel free to correct me. :)
The faster/slower meet for the first time SOMEWHERE in the cycle, but not necessarily at the first (thus repeated) element. That's why you need the second step, where you move fast back to the start and advance it and slow both slowly (1 at a time). At this point we know that as soon as fast enters the loop, it will be pointing at the same element as slow, so we can use this to identify the first element, which we know must be the repeated element.
@LinMa If k is the move where fast and slow meet for the first time, then after k moves fast has move 2k steps, and slow has moved k steps. Now we move fast back to zero and start moving it 1 step per move instead of 2. Starting from 0, in k 1-step moves it is in position k. Slow started out in position k, so in another k 1-step moves it is in position 2k. We already know that position 2k is the same as position k.
@LinMa Let's say that we start with fast moving twice per second, and slow moving once per second, and that they meet after k seconds on some spot in the loop whiche I'll call x. Then we reset fast to zero and change it's speed to move once per second. So now fast and slow are moving at the same speed. In another k seconds, they'll both be back at x. The thing to notice here is that if we unwind the clock by one second, then they'll both move backwards at the same speed, so as long as fast is still in the loop, it will equal slow.
|
1

Since you cannot use any additional space, using another hash table would be ruled out.

Now, coming to the approach of hashing on existing array, it can be acheived if we are allowed to modify the array in place.

Algo:

1) Start with the first element.

2) Hash the first element and apply a transformation to the value of hash.Let's say this transformation is making the value -ve.

3)Proceed to next element.Hash the element and before applying the transformation, check if a transformation has already been applied.

4) If yes, then element is a duplicate.

Code:

 for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      cout<< abs(arr[i]) <<endl;
  }

This transformation is required since if we are to use hashing approach,then, there has to be a collision for hashing the same key.

I cant think of a way in which hashing can be used without any additional space and not modifying the array.

Improve this answer

3 Comments

You cannot modify the existing array.
"I cant think of a way in which hashing can be used without any additional space and not modifying the array."...agreed.if hashing is to be used, then the array will have to be modified or else it's not possible.
@basav, ideas is smart and agree with n.m. and we should not modify the array. Thanks for the sharing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.