# My O(n) solution using XOR

• 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;
}
``````

`

• exactly :) XOR is always the trick

• Cool. recall me the bitwise operations

• The best answer!

• 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).

• more basic!good answer.

• Can someone explain to me what "n" means here? Is it the length of the array or just some random number? The original class doesn't have the "int n" parameter. I'm quite confused here although I understand the algorithm..

• best one!!! great XOR

• This is the best answer!

• The simple and novel answer ! Easy to understand.

• My God! Such a simple answer!

• genius, and I was pulling my hair on this one (I even considered XOR, arghh!)

• This post is deleted!

• 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?

• Indeed, the problem's wording is bad.

• 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?

• Brilliant! But I think you should handle the case when the single number is 0. If you set result as 0 in the beginning, it may not work.
I think result should be set as A[0] and the loop starts from i = 1 instead.

• It doesn't matter. When a number XOR 0, the result is still itself.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.