Find all odd occurring elements in an array having limited range of elements

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


 

For example,


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

Download   Run Code

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Guest
Guest

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

viperx
Guest

#include
using namespace std;

int main() {
// your code goes here
int n;
cin>>n;
vector v(n+1);

// no. between 1 to 31

int XOR = 0;
for(int i=0;i>v[i];
XOR ^= (1<<v[i]);
}

for(int i=0;i<32;i++) {
if(XOR &(1<<i)) {
cout<<i<<" ";
}
}
cout<<endl;

return 0;
}