Find two repeating elements in the given array

Question

You are given an array of n + 2 elements. All elements of the array are in the range from 1 to n. And all elements occur once, except for two numbers that occur twice. Find two repeating numbers.

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

Guys I know 4 possible solutions to this problem, but recently I came across a solution that I cannot interpret. Below is a solution algorithm

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 // ie, 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])] ie,A[1] is positive ; so make it negative ; so list now is {-1,1,2,3,2} i=2 ; A[abs(A[2])] ie, A[1] is negative ; so A[i] ie, 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 gives the correct results, i.e. how it works. Gyys does not take this as a homework question, as this question was recently asked in an interview with Microsoft.

Answer 1

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

Let's change this value a bit and move on only with n , not n+2 , and the first part of the problem statement will become

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

So, now you know that you have an array, the numbers in the array start at 1 and go up one for each element of the array. So, if you have 10 elements, the array will contain numbers from 1 to 10. 5 elements, you have from 1 to 5, etc.

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

Now add in one duplicate number. The algorithm takes the value of each number in the array and visits this index. We know that if we visit the same index twice, we know that we 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 that we visit, if the sign has already changed, we know that we are already here, ergo, this index (and not the value stored in the index) is a duplicate number.

You can achieve the same result by storing a second array of booleans initialized to false. This algroism is becoming

 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 change the sign of the element in instead of setting the boolean to B.

Hope this helps,

Answer 2

What you do uses the values ​​of the array in two ways: they have a number And they have a sign. You "store" the fact that you saw the number n at the nth place in your array, without losing the original value in this place: you just change the sign.

You start with all the positive results, and if you find that your index that you want to “save”, the fact that you have already seen the current value, is already negative, then this value was already visible.

Example: So, if you see 4 for the first time, you change the sign in fourth place to negative. This does not change 4th place, because you use [abs] when you are there, so do not worry. If you see 4 more, you will again check 4th place, look that it is negative: presto: double.

Answer 3

When you find some element in position i, say n, then you make A[abs(A(i))]=A[abs(n)] negative. Therefore, if you find another position j containing n, you also check A[abs(A(j))]=A[abs(n)] . Since you think this is negative, then n is repeated :)

Answer 4

Simple, use a hashtable.

For each element, make sure that it already exists O (1), and if not, add it to the O (1) hash table.

When you find an element that already exists ... that is it.

Answer 5

I know that this is not really the answer to your question, but if I really needed to write this code in a real project, I would start by sorting algo as 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 put this in the basket of a “good balance between performance and maintainability” of possible solutions.