Given an array having elements between 0 to 31, find elements which occurs odd number of times without using the extra space.

**Input:** { 5, 8, 2, 5, 8, 2, 8, 5, 1, 8, 2 }

**Output:** The odd occurring elements are: 5, 2, and 1

**Explanation:**

5 occurs 3 times

8 occurs 4 times

2 occurs 3 times

1 occurs 1 times

A simple solution would be to store frequencies of elements of the array in a count array or a map and print elements that have odd frequencies. The advantage of this approach is that it can work on any range of input but it requires extra space.

In order to solve this problem in constant space, bitwise XOR operator can be used. We know that result of a XOR operation is 0 if both first bit and second bit are 0 or both are 1, and the result is 1 only if only either the first bit is 1 or only the second bit is 1.

To illustrate, consider the input array `A[] = { 5, 8, 2, 5, 8, 2, 8, 5, 1, 8, 2 }`. If we consider each element of the array, right shift 1 by its value, and take XOR of all the results, we will get `00000000 00000000 00000000 00100110`.

Each 1 at the i’th index from the right represents odd occurrence of element i and each 0 at the i’th index from the right represents even or non-occurrence of element i in the array. So, the odd occurring elements are 1, 2, and 5 since 1 holds 1st, 2nd, and 5th position.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <stdio.h> // Find odd occurring elements in the given array void findRepeating(int A[], int n) { int xor = 0; for (int i = 0; i < n; i++) xor ^= (1 << A[i]); printf("The odd occurring elements are: "); for (int i = 0; i < n; i++) { if (xor & (1 << A[i])) { printf("%d ", A[i]); xor ^= (1 << A[i]); // to avoid printing duplicates } } } // main function int main(void) { int A[] = { 5, 8, 2, 5, 8, 2, 8, 5, 1, 8, 2 }; int n = sizeof(A) / sizeof(A[0]); findRepeating(A, n); return 0; } |

`Output: `

The odd occurring elements are: 5 2 1

**Exercise:**

1. Extend the solution for finding even occurring elements.

2. Extend the solution for handling the range 0 to 63

**Author:** Aditya Goel

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Second for loop can be optimized by iterating the for loop from 0 to 31