Find odd occurring element in a given array

Problem: Given an array of integers, all numbers occur even number of time except one number which occurs odd number of time. Find the number occurring odd number of times. Write a program to solve this problem in O(n) time complexity and using constant O(1) extra space.

For example:

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

A Naive Solution is to run two nested loops. The outer loop picks all elements one by one and inner loop counts number of occurrences of the element picked by outer loop. Time complexity of this solution is O(n²).

We can also solve this problem using hash table in O(n). We initially traverse the array and maintain frequency of each elements. Later traverse the hash table and print the number having off frequency. However we are able to solve the problem in O(n), we also require O(n) extra space.

The best way to do this type of problem is to use bitwise XOR. 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 all elements gives us odd occurring element.

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

int getOdd(int ar[], int ar_size)
{
    int i, res = 0;
    for (i=0; i < ar_size; i++)
    {
        /* taking xor of each number */
        res = res ^ ar[i];
    }

    return res;
}

/* Diver function */
int main()
{
     int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};

     int n = sizeof(ar)/sizeof(ar[0]);
     cout<<getOdd(ar, n)<<"\n";

     return 0;
}

Output:

5