Find the two repeating elements in a given array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. F开发者_JAVA技巧ind the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

Guys I know 4 probable solutions to this problem but recently i encountered a solution which i am not able to interpret .Below is an algorithm for the solution

traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}
Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition,
now list is {-1,1,2,3,2}

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated
now list becomes {-1,-1,-2,3,2}

i=4 ;
and A[4]=3 is not repeated

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition,

This method modifies the original array.

How this algorithm is producing proper results i.e. how it is working.Guys don't take this as an Homework Question as this question has been recently asked in Microsoft's interview.

---

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice

Lets modify this slightly, and go with just n, not n+2, and the first part of the problem statement, it becomes

You are given an array of n elements. All elements of the array are in range 1 to n

So now you know you have an array, the numbers in the array start at 1 and go up by one for every item in the array. So if you have 10 items, the array will contain the numbers 1 to 10. 5 items, you have 1 to 5 and so forth.

It follows that the numbers stored in the array can be used to index the array. i.e. you can always say A[A[i]] where i <= size of A. e.g. A={5,3,4,1,2}; print A[A[2]]

Now, lets add in one duplicate number. The algorithm takes the value of each number in the array, and visits that index. We know if we visit the same index twice, we know we have found a duplicate.
How do we know if we visit the same index twice?
Yup, we change the sign of the number in each index we visit, if the sign has already changed, we know we've already been here, ergo, this index (not the value stored at the index) is a duplicate number.

You could achieve the same result by keeping a second array of booleans, initialised to false. That algroithm becomes

A={123412}
B={false, false, false, false}

for(i = 1; i <= 4; i++)
{
    if(B[A[i]])
       // Duplicate
    else
       B[A[i]] = true;
}

However in the MS question you're changing the sign of the element in A instead of setting a boolean value in B.

Hope this helps,

---

What you are doing is using the array values in two ways: they have a number AND they have a sign. You 'store' the fact that you've seen a number n on the n-th spot in your array, without loosing the origional value in that spot: you're just changing the sign.

You start out with all positives, and if you find that your index you want to 'save' the fact you've seen your current value to is allready negative, then this value has allready be seen.

example: So if you see 4 for the first time, you change the sign on the fourth spot to negative. That doesn't change the 4th spot, because you are using [abs] on that when you would go there, so no worries there. If you see another 4, you check the 4th spot again, see that it is negative: presto: a double.

---

When you find some element in position i, let's say n, then you make A[abs(A(i))]=A[abs(n)] negative. So if you find another position j containing n, you will also check A[abs(A(j))]=A[abs(n)]. Since you find it negative, then n is repeated :)

---

the best approach for finding two repeated elements would be using XOR method.

This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 1 to n. As we know A XOR A = 0. We have n + 2 elements in array with 2 repeated elements (say repeated elements are X and Y) and we know the range of elements are from 1 to n. XOR all the numbers in array numbers from 1 to n. Result be X XOR Y. 1 XOR 1 = 0 and 1 XOR 0 = 1 with this logic in the result of X XOR Y if any kth bit is set to 1 implies either kth bit is 1 either in X or in Y not in both. Use the above step to divide all the elements in array and from 1 to n into 2 groups, one group which has the elements for which the kth bit is set to 1 and second group which has the elements for which the kth bit is 0. Let’s have that kth bit as right most set bit (Read how to find right most set bit) Now we can claim that these two groups are responsible to produce X and Y. Group -1: XOR all the elements whose kth bit is 1 will produce either X or Y. Group -2: XOR all the elements whose kth bit is 0 will produce either X or Y. See the diagram below for more understanding.(Click on the diagram to see it larger).

public class TwoRepeatingXOR {
public static void twoRepeating(int [] A, int n){
    int XOR = A[0];
    int right_most_bit, X=0, Y=0, size = A.length;

    for (int i = 1; i <=n ; i++)
        XOR ^= i;

    for (int i = 0; i <size ; i++)
        XOR ^= A[i];

    //Now XOR contains the X XOR Y
    //get the right most bit number
    right_most_bit = XOR & ~(XOR-1);
    //divide the elements into 2 groups based on the right most set bit
    for (int i = 0; i <size ; i++) {
        if((A[i] & right_most_bit)!=0)
            X = X^A[i];
        else
            Y = Y^A[i];
    }
    for (int i = 1; i <=n ; i++) {
        if((i&right_most_bit)!=0)
            X = X^i;
        else
            Y = Y^i;
    }
    System.out.println("Two Repeated elements are: " + X + " and " + Y);
}
public static void main(String[] args) {
    int [] A = {1,4,5,6,3,2,5,2};
    int n = 6;
    twoRepeating(A, n);
}
}

credits go to https://algorithms.tutorialhorizon.com/find-the-two-repeating-elements-in-a-given-array-6-approaches/

---

Simple, use a Hashtable.

For each item, check if it already exists O(1) , and if not, add it to the hashtable O(1).

When you find an item that already exists... that's it.

---

I know this isn't really an answer to your question, but if I actually had to write this code on a real project, I would start with a sort algo like quicksort, and in my comparison function something like,

int Compare(int l, int r)
{
    if(l == r)
    {
        // duplicate; insert into duplicateNumbers array if it doesn't exist already.
        // if we found 2 dupes, quit the sort altogether
    }
    return r - l;
}

I would file this into the "good balance between performance and maintainability" bucket of possible solutions.