How to find a 2 unpaired elements in array?

Question

You have an array with n=2k+2 elements where 2 elements haven't pair. Example for 8 elemets array: 1 2 3 47 3 1 2 0. "47" and "0" haven't pair in array. If I have array where only 1 element has't pair, I solve this problem with XOR. But I have 2 unpair elements! What can I do? Solution could be for a O(n) time performance and for O(1) additional memory.

Answer 1

1. Scan the Array and put each number and count in hash.
2. Rescan and find out the items with count=1.

This is O(n).

Answer 2

Use INT_MAX/8 bytes of memory. Walk the array. XOR the bit corresponding to each value with 1. If there are 0 or 2 instances the bit will end up 0. If there is only one instance, it will be set. O(1) mem, O(N) time.

Answer 3

Some hints...

It will take 2 passes. First, go through the list and XOR all elements together. See what you get. Proceed from there.

Edit: The key observation about the result of the first pass should be that it shows you the set of bits in which the 2 unpaired elements differ.

Answer 4

You can try this.It will take O(n) time

        int xor = arr[0];
        int set_bit_no;
        int i;
        int x = 0; //First unpair number
        int y = 0; //second unpair number
        for (i = 1; i < n; i++)
            xor ^= arr[i];

        set_bit_no = xor & ~(xor-1);//Get the rightmost set bit in set_bit_no
        for (i = 0; i < n; i++)
        {
            if (arr[i] & set_bit_no) {
                //XOR of first set 
                x = x ^ arr[i];
            }
            else
            {
                //XOR of second set
                y = y ^ arr[i];
            }
        }

Explanation... arr[] = {2, 4, 7, 9, 2, 4} 1) Get the XOR of all the elements. 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. set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010 Now set_bit_no will have only set as rightmost set bit of xor. 3) 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.