2

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}

  1. XOR every element. xor = 2^4^7^9^2^4 = 14 (1110)
  2. 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.
  3. set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010. Now set_bit_no will have only set as rightmost set bit of xor.
  4. 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.
Improve this question
9
  • If you already know the algorithm maybe you can show it here. In particular, which step do you not understand? Commented Aug 30, 2015 at 10:45
  • @MichielUitHetBroek I'm not able to understand step 2 & 3 of above example Commented Aug 30, 2015 at 11:02
  • 1
    @Preetib See if can understand this explanation. 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. Commented Aug 30, 2015 at 11:11
  • @PauloAlmeida this is an entirely different problem. One has two elements repeated, the other has all elements except two repeated. Commented Aug 30, 2015 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. Commented Aug 30, 2015 at 11:21

1 Answer 1

Reset to default
2

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.