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.

Answer 1

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,

Answer 2

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.

Answer 3

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