CareerCup

Take XOR of all the numbers of array. Resulting number in XOR is the answer.

You can do this in O(nlgn) by sorting the array and searching

To do it in O(n) I think you need O(n) extra space. You can use a hash map and then hash the numbers as you see. If the number is not present in the HashMap, you add it. If it is already present you remove it. In the end the only number remaining in the hash map will be the number you need.

XOR all numbers.

XOR all the numbers and get the result in O(n) with no extra space

As the others pointed out, just use XOR. Example in Java

private static int findOddRepXor(int[] a) {	
	    int val = 0;
	    for (int i = 0; i < a.length; i++){
	        val = val ^ a[i];
	    }
	    return val; 
	}

The Logic Is if Number Is repated Even Number Of Times Then By Doing Xor It Becomes 0.But The Odd Number Times Element By Doing Xor It gives ItS value.
#include<stdio.h>
int arr[]={5,4,3,3,4,1,1};
main()
{
int i,count=0;
for(i=0;i<=6;i++)
{
count^=arr[i];
}
printf(" %d",count);
}