Find the two repeating elements in a given array

Question

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

@leppie this is another problem, as there are TWO repeated numbers — Dr. belisarius, Feb 01 '11 at 07:37
@leppie I was tempted too :D. BTW this algorithm is clever ... — Dr. belisarius, Feb 01 '11 at 07:40
@belisarius: Without trying to understand it, what is it's complexity? And how does it compare to a solution using merge sort then simple traversal (which would be `O(n log n)`)? — leppie, Feb 01 '11 at 07:42
@belisarius: Ah ok, pretty simple actually now that I bothered to read it :) — leppie, Feb 01 '11 at 07:55
@leppie: Same subject matter, but a different question. Your possible duplicate is asking for solutions (and yours is excellent +1 BTW). This question is asking for an explanation for a specific solution. — Binary Worrier, Feb 01 '11 at 07:55
@leppie: I'll leave mine there in case the `close(1)` attaracts attention by it's self (I've more than once wished for an *Undo Close* option) — Binary Worrier, Feb 01 '11 at 08:00
possible duplicate of [Algorithm to find two repeated numbers in an array, without sorting](http://stackoverflow.com/questions/555744/algorithm-to-find-two-repeated-numbers-in-an-array-without-sorting) — moinudin, Feb 01 '11 at 09:41
Related to http://stackoverflow.com/questions/3887278/puzzle-finding-out-repeated-element-in-an-array — AShelly, Feb 01 '11 at 22:57

score 18 · Accepted Answer · edited Feb 01 '11 at 08:41

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,

+1. For me, it takes your explanation to understand the other explanations. — Lieven Keersmaekers, Feb 01 '11 at 08:44
@yogi15490: You're more than welcome sir (If you're happy that this answers your question, you could mark it as the Accepted Answer, thanks). — Binary Worrier, Feb 01 '11 at 11:44

score 2 · Answer 2 · answered Feb 01 '11 at 07:32

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.

zfm · Answer 3 · 2011-02-01T08:20:07.917

1

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 :)

edited Feb 01 '11 at 08:20

answered Feb 01 '11 at 07:39

zfm

1,906
2
17
28

score 1 · Answer 4 · answered Jun 23 '21 at 12:32

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

This solution works only if array has positive integers and all the elements 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/

score 0 · Answer 5 · answered Feb 01 '11 at 17:28

0

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.

answered Feb 01 '11 at 17:28

Yochai Timmer

48,127
24
147
185

score 0 · Answer 6 · answered Feb 01 '11 at 17:43

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.

Find the two repeating elements in a given array

6 Answers6