Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

find duplicate number in an array

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;
}
like image 646
Lin Ma Avatar asked Oct 19 '15 05:10

Lin Ma


People also ask

How can I find duplicate number?

Find the Duplicate Number - LeetCode. Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums , return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.

How do you check if there are duplicates in an array java?

One more way to detect duplication in the java array is adding every element of the array into HashSet which is a Set implementation. Since the add(Object obj) method of Set returns false if Set already contains an element to be added, it can be used to find out if the array contains duplicates in Java or not.

How do you find duplicate objects in an array?

Using the indexOf() method In this method, what we do is that we compare the index of all the items of an array with the index of the first time that number occurs. If they don't match, that implies that the element is a duplicate. All such elements are returned in a separate array using the filter() method.


3 Answers

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].

like image 84
Khatri Avatar answered Oct 21 '22 12:10

Khatri


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.

like image 34
keithmo Avatar answered Oct 21 '22 13:10

keithmo


  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.
like image 37
Dave Avatar answered Oct 21 '22 13:10

Dave