Tuesday, 1 July 2014

Find an element occuring odd number of times

Given an array a, find an element occuring odd number of times, all other elements occur even number of times

Approach

XOR all the elements of an array, the result will be the element occuring odd number of times. (Refer http://en.wikipedia.org/wiki/Bitwise_XOR#XOR for more information on XOR)

Input:       An array of size n.
Output:    Elements that appear odd number of times

Example: 
Input:       7
                1,2,3,3,2,6,1
Output:    6 


#include<iostream>
using namespace std;

int FindElement ( int * a, int n )
{
    int res=0;
    for ( int i=0; i<n; i++ )
    {
        res^=a[i];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    int *a=new int[n];
    for ( int i=0; i<n; i++ )
    {
        cin>>a[i];
    }
    cout<< FindElement ( a,n );
    free ( a );

    getchar();

}


Please comment if you find anything incorrect or have any other inputs.

No comments:

Post a Comment