Given an array of integers, duplicates are present in it in such a way that all duplicates appear even number of times except one which appears odd number of times. Find that odd appearing element in linear time and without using any extra memory.

For example,

**Input: ** arr = [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3]

** Output: **Odd occurring element is 4

We can use hashing to solve this problem in O(n) time. We initially traverse the array and maintain frequency of each element in a hash table. Then after all array elements are processed, we return the element with the odd frequency. The problem with this approach is that it requires O(n) extra space as well. Also it requires one traversal of array and one traversal of hash table.

We can solve this problem in one traversal of array and in O(1) space. The idea is to use XOR operator. 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 x with 0

x ^ 0 = x

XOR x with itself even number of times

x ^ x = 0

x ^ x ^ x ^ x = (x ^ x) ^ (x ^ x) = 0 ^ 0 = 0

XOR x with itself odd number of times

(x ^ x ^ x) = (x ^ (x ^ x)) = (x ^ 0) = x

(x ^ x ^ x ^ x ^ x) = (x ^ (x ^ x) ^ (x ^ x)) = (x ^ 0 ^ 0) = x

So, if we take XOR of all elements present in the array, even appearing elements will cancel each other and we are left with the only odd appearing element.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <stdio.h> // Function to find odd occurring element in a given array int findOddOccuring(int arr[], int n) { int xor = 0; for (int i = 0; i < n; i++) xor = xor ^ arr[i]; return xor; } // main function int main() { int arr[] = { 4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Odd occurring element is %d", findOddOccuring(arr, n)); return 0; } |

`Output:`

Odd occurring element is 4

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <numeric> // Function to find odd occurring element in a given array int findOddOccuring(int arr[], int n) { return std::accumulate(arr, std::next(arr, n), 0, std::bit_xor<>{}); } // main function int main() { int arr[] = { 4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3 }; int n = sizeof(arr) / sizeof(arr[0]); std::cout << "Odd occurring element is " << findOddOccuring(arr, n); return 0; } |

`Output:`

Odd occurring element is 4

**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

Hi, just a solution using std::accumulate and std::bit_xor:

https://ideone.com/LEqki6

Thanks for suggesting this. We have added your solution in the post. Happy coding 🙂

It is also possible to solve the problem in linear time if there are

twounpaired elements.You’ll need more than one pass, but the total is still O(n)

For an array having more than >=2 numbers that occur odd times, I can think of a solution using unordered_map (O(n) complexity). However, I cannot find a solution for it using XOR operator. Anybody has any idea?