known that A XOR A = 0 and the XOR operator is commutative, the solution will be very straightforward.
`
int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++)
{
result ^=A[i];
}
return result;
}
`
For anyone who didn't understood why this works here is an explanation. This XOR operation works because it's like XORing all the numbers by itself. So if the array is {2,1,4,5,2,4,1} then it will be like we are performing this operation
((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5.
Hence picking the odd one out ( 5 in this case).
Thank you for the simple answer. Very neat.
I am just wondering what if the array was [1,1,2,2,2,2,3,3]? In this case, the integer 2 happened four times (obviously more than twice), but 2^2^2^2 = 0. It seems that this solution requires an extra condition: the number of occurrences of the answer must be odd?
sorry if it's a dumb question. I'm not really good at this.
May I ask if the XOR operation will ignore the order of the list? I mean, what would I get if I XOR [2,1], then XOR the result with [4]? At the end of day, is it true that as long as there are repeats, the XOR result will only pick the odd one out disregard the order?