CareerCup

#include<iostream>

using namespace std;

int main()
{
    int arr[] = { 1,2,1,2,5,3,4,3,4,1,2,1,2};

    int v = 0;

    for(int i=0;i<(sizeof(arr)/sizeof(int));i++)
    {
        v ^= arr[i];
    }

    cout << v << endl;

    return 0;
}

@AmzFAILFacebookFailMSFTFail: please accept my apologies for not providing the explanation.
xor'ing a number with itself even number of times will results in a 0 and xor'ing the number with itself odd number of times will results in the number itself. I have used this nature of xor operation to reach to this result.

void findOdd(int *a ,int n)
{
//sort array with O(nlogn)
int count=0; int x=a[0];
for(int i=0;i<n;i++)
{
if(a[i]!=x)
{
if((count%2)!=0)
{cout<<a[i]; return;}
else
{x=a[i]; count=1;}
}
else
count++;
}

doing XOR operation will get the number which has been repeated odd number of times.XOR cancels the even repetetions

Again, how about a hashmap.
Add each of the elements to the hashmap on its first occurrence and remove it from the hashmap on its second occurrence. This way at the end only the object of our interest remains in the hashmap and can be found easily.

Time Complexity:O(n)
Space Complexity:O(n)