Take XOR
of all the elements.
The pairs will cancel out as
a XOR a = 0
and the result will be the only unpaired element as
0 XOR a = a
If its okay to destroy the array you can XOR
adjacent elements. Once done the last element of the array has the unpaired element:
N = Num of elements in array.
for( i=1 to N )
arr[i] ^= arr[i-1];
print arr[N-1]
If its not okay to destroy the array, you can make use of a variable to hold the result:
N = Num of elements in array.
Unpaired = arr[0];
for( i=1 to N )
Unpaired = Unpaired ^ arr[i];
print Unpaired
C function to do the same:
int findUnpaired(int *arr,int len) {
int i; // loop counter.
int unpaired; // to hold the unpaired element.
unpaired = arr[0]; // initialize it with the 1st array ele.
for(i=1;i<len;i++) { // loop for all remaining elements.
unpaired ^= arr[i]; // XOR each element with the running XOR.
}
return unpaired; // return result.
}