# My Java solution in O(n) time complexity and O(1) space complexity using XOR

• ``````public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int num : nums) {
res ^= num;
}
return res;
}
}``````

• I'm sure for a lot of people this may be confusing as to why this works. The idea hinges on 3 properties of xor. (1) that its a commutative operation (i.e. a xor b = b xor a). (2) that something xor itself is 0. So a xor a = 0. And (3) 0 xor a = a. These three properties mean that

a xor b xor a = a xor a xor b = 0 xor b = b.

Thus it doesn't matter the order of the numbers. If something only occurs once it won't get negated.

• I wonder if the complexity of this algo is really O(n). It seems like O(n * length of binary number)

• We only need to calculate the times that res ^= num; is called. We do not need to know the times of the bit operation for each bit so the time complexity is O(n).

• nice explain, thanks

• @marrvolo
The XOR operation is one single machine operation, it doesn't matter the length of binary number.

Also, in Big O(), O(n) is equivalent as O(x*n), the complexity remains linear which is what we care most of the time.

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