Find 2 repeating elements in given array

Question

Given an array with n+2 elements, all elements in the array are in the range 1 to n and all elements occur only once except two elements which occur twice.

Find those 2 repeating numbers. For example, if the array is [4, 2, 4, 5, 2, 3, 1], then n is 5, there are n+2 = 7 elements with all elements occurring only once except 2 and 4.

So my question is how to solve the above problem using XOR operation. I have seen the solution on other websites but I'm not able to understand it. Please consider the following example:

arr[] = {2, 4, 7, 9, 2, 4}

XOR every element. xor = 2^4^7^9^2^4 = 14 (1110)
Get a number which has only one set bit of the xor. Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010. Now set_bit_no will have only set as rightmost set bit of xor.
Now divide the elements in two sets and do xor of elements in each set, and we get the non-repeating elements 7 and 9.

If you already know the algorithm maybe you can show it here. In particular, which step do you not understand? — Michiel uit het Broek, Aug 30 '15 at 10:45
@MichielUitHetBroek I'm not able to understand step 2 & 3 of above example — Preetib, Aug 30 '15 at 11:02
@Preetib See if can understand [this explanation](http://stackoverflow.com/a/22953668/1081569). The idea is that if you XOR all the elements in the list with a list of 1 to n, the result is the XOR of the duplicated elements (because the others cancel themselves). Then you take a bit that is set in that XOR, which means it is different in the duplicated elements, and split the numbers in two groups, according to whether they have that bit set or not. Finally, you XOR each of those groups and all the numbers cancel themselves out except for those you are looking for. — Paulo Almeida, Aug 30 '15 at 11:11
@PauloAlmeida this is an entirely different problem. One has two elements repeated, the other has all elements except two repeated. — n. m. could be an AI, Aug 30 '15 at 11:16
@n.m. Yes, but you can frame it in the same way. You just add another array of 1 to n elements and now you have all the elements repeated and two elements occurring three times. The only requirement is that you have at most two elements appearing an odd number of times. — Paulo Almeida, Aug 30 '15 at 11:21
@n.m. Of course it's crucial that in this formulation of the problem they say that all the elements are in the array ranging from 1 to n. Otherwise you couldn't do what I said in my previous comment. — Paulo Almeida, Aug 30 '15 at 11:24
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/88299/discussion-between-paulo-almeida-and-n-m). — Paulo Almeida, Aug 30 '15 at 11:24
Your final example is inconsistent with the specs. If `arr == [2, 4, 7, 9, 2, 4]`, then `n == 4`, so 7 and 9 are not allowed to appear. You probably want to replace 7 and 9 with 1 and 3. — Filipe Gonçalves, Aug 30 '15 at 14:04

score 2 · Answer 1 · edited May 23 '17 at 12:06

Yes, you can solve it with XORs. This answer expands on Paulo Almeida's great comment.

The algorithm works as follows:

Since we know that the array contains every element in the range [1 .. n], we start by XORing every element in the array together and then XOR the result with every element in the range [1 .. n]. Because of the XOR properties, the unique elements cancel out and the result is the XOR of the duplicated elements (because the duplicate elements have been XORed 3 times in total, whereas all the others were XORed twice and canceled out). This is stored in xor_dups.

Next, find a bit in xor_dups that is a 1. Again, due to XOR's properties, a bit set to 1 in xor_dups means that that bit is different in the binary representation of the duplicate numbers. Any bit that is a 1 can be picked for the next step, my implementation chooses the least significant. This is stored in diff_bit.

Now, split the array elements into two groups: one group contains the numbers that have a 0 bit on the position of the 1-bit that we picked from xor_dups. The other group contains the numbers that have a 1-bit instead. Since this bit is different in the numbers we're looking for, they can't both be in the same group. Furthermore, both occurrences of each number go to the same group.

So now we're almost done. Consider the group for the elements with the 0-bit. XOR them all together, then XOR the result with all the elements in the range [1..n] that have a 0-bit on that position, and the result is the duplicate number of that group (because there's only one number repeated inside each group, all the non-repeated numbers canceled out because each one was XORed twice except for the repeated number which was XORed three times).

Rinse, repeat: for the group with the 1-bit, XOR them all together, then XOR the result with all the elements in the range [1..n] that have a 1-bit on that position, and the result is the other duplicate number.

Here's an implementation in C:

#include <assert.h>

void find_two_repeating(int arr[], size_t arr_len, int *a, int *b) {
    assert(arr_len > 3);
    size_t n = arr_len-2;
    int i;

    int xor_dups = 0;
    for (i = 0; i < arr_len; i++)
        xor_dups ^= arr[i];
    for (i = 1; i <= n; i++)
        xor_dups ^= i;

    int diff_bit = xor_dups & -xor_dups;
    *a = 0;
    *b = 0;

    for (i = 0; i < arr_len; i++)
        if (arr[i] & diff_bit)
            *a ^= arr[i];
        else
            *b ^= arr[i];

    for (i = 1; i <= n; i++)
        if (i & diff_bit)
            *a ^= i;
        else
            *b ^= i;
}

arr_len is the total length of the array arr (the value of n+2), and the repeated entries are stored in *a and *b (these are so-called output parameters).

I didn't answer because I thought it was close to a duplicate of the question I linked to, but +1 for the extended explanation and implementation. — Paulo Almeida, Aug 30 '15 at 16:39

Find 2 repeating elements in given array

1 Answers1