Finding the element occurring odd number of times

You can find a similar question in interviews which is infact a specific problem of the above category. An array contains 2n+1 positive integers where n integers appear twice, and one integer appear only once. Find that integer.

For example if the input array is [1,1,2,2,3] the output should be 3.

Whenever you encounter these kind of problems, think of XOR based solution. The following table shows the XOR logic of two bits

A  B   Result
————–
0  0     0
0  1     1
1  0     1
1  1     0
This problem can easily be solved using the same logic. We all know that, performing XOR between the same bit pattern results in all Zeroes.
For example let us consider the bit pattern for 133

10000101
10000101
———
00000000

Performing XOR between a bit pattern and all zeros gives the same bit pattern.
For example let us XOR 133 and 0

10000101
00000000
——–
10000101
And we also know that XOR is an associative and Commutative operation.
i.e A XOR (B XOR C) = (A XOR B) XOR C
    A XOR B = B XOR A

This means that if we XOR all the elements in the array, all the elements occurring even number of times nullify each other and only the number appearing odd number of times remains.

So the following simple program solves this problem.

#include <iostream>
#define MAXSIZE 100
int array[MAXSIZE];
using namespace std;
int findOddOccur(int n)
{
 int res = 0;
 for( int i = 0 ; i < n ;i++)
 {
  res = res ^ array[i];
 }
 return res;
}
int main()
{
 int n;
 cin>>n;
 for( int i = 0 ; i < n ; i++)
 {
  cin>>array[i];
 }
 cout<<"Odd occuring element is: "<<findOddOccur(n);
 return 0;
}