Find two odd occurring element in an unsorted array

Problem: Given an array of integers, each number in the array occur even number of times except two numbers that occur number of times. Find both odd appearing element without using any extra memory.

For example:

Input: arr = {4, 3, 6, 2, 4, 2, 3, 4, 3, 3}
Output: 4 and 6

Input: arr = {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

Input: arr = {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}
Output: 100 and 5000

A Naive method to solve this problem is to run two nested loops. The outer loop picks an element and the inner loop counts the number of occurrences of the picked element. If the count of occurrences is odd then print the number. The time complexity of this method is O(n²).

Other improved method is to use sorting to get the odd occurring numbers in O(nLogn) time. First sort the numbers using an O(nLogn) sorting algorithm like Merge Sort, Heap Sort, quickSort, etc. Once the array is sorted, all we need to do is a linear search of the array and print the odd occurring number.

We can also use hashing to solve this problem in O(n) time. The idea is to traverse the array and maintain frequency of each element in a hash table. After all array elements are processed, we return the elements with odd frequencies. The problem with this approach is that it requires O(n) extra space.

There is a better approach to solve this problem using bitwise XOR in O(n) time complexity and O(1) extra space. We know that if we XOR a number with itself odd number of times the result is number itself, otherwise if we XOR a number even number of times with itself, the result is 0. Also XOR with 0 is always the number itself.

• XOR of any number n with itself gives us 0, i.e., n ^ n = 0 
• XOR of any number n with 0 gives us n, i.e., n ^ 0 = n 
• XOR is cumulative and associative. 

So, if we take XOR of all elements present in the array, even appearing elements will cancel out each other and we are left with XOR of x and y (x ^ y) where x and y are two odd appearing elements. 

Finding x and y :

Let result = (x ^ y) We know that any set bit in result will be either set in x or y (but not in both as a bit will only set in result when it is set in one number and unset in the other). For example, if x = 6 (0110) and y is 15 (1111), then result will be (1001), the two set bits in result indicate that the corresponding bits in x and y are different.

The idea is to consider the rightmost set bit in result (or any other set bit) and split the array into two sub-arrays –

• All elements that have this bit set. 
• All elements that have this bit unset. 

As this rightmost bit is set in one number and unset in the other, we will have one odd appearing element in each sub-array. Basically we have isolated trait of one number with other so that both x and y will go to different sub-array. Now we iterate each sub-array once more, do XOR on each element of the sub-array and the result will be the odd appearing element present in the sub-array (since even appearing elements will cancel each other).

#include <bits/stdc++.h>
using namespace std;

pair<int, int> findOdd(int arr[], int n)
{
    int result = 0;

    /* taking XOR of all array elements */
    for (int i = 0; i < n; i++)
        result = result ^ arr[i];

    /* finding position of the rightmost set bit in result */
    int k = log2(result & -result);

    /* x and y are two odd appearing elements */
    int x = 0, y = 0;

    /* split the array into two sub-arrays */
    for (int i = 0; i < n; i++)
    {
        /* elements that have k'th bit 1 */
        if (arr[i] & (1 << k))
            x = x ^ arr[i];

        /* elements that have k'th bit 0 */
        else
            y = y ^ arr[i];
    }

    return make_pair(x, y);
}

/* Driver function */
int main()
{
    int arr1[] = { 4, 3, 6, 2, 4, 2, 3, 4, 3, 3 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    pair<int, int> p1 = findOdd(arr1, n1);
    cout<< p1.first << " and " << p1.second <<"\n";

    int arr2[] = { 12, 23, 34, 12, 12, 23, 12, 45 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    pair<int, int> p2 = findOdd(arr2, n2);
    cout<< p2.first << " and " << p2.second <<"\n";

    int arr3[] = {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);

    pair<int, int> p3 = findOdd(arr3, n3);
    cout<< p3.first << " and " << p3.second <<"\n";

    return 0;
}

Output:

6 and 4
45 and 34
100 and 5000