# O(n) time without extra space - Java

• ``````public int singleNumber(int[] nums) {
if(nums.length == 1) {
return nums[0];
}
for(int i = 1; i < nums.length; i++) {
nums[0] ^= nums[i];
}
return nums[0];
}
``````

• Could you explain why this algorithm will work?I am so interested in the operator ^!Thank you!

• because the xor has three properties. 1,0^a=a 2,a^b=b^a 3,a^a=0
so swapping the number would not change the output at the end, we can see the list as all the same numbers are adjacent. the same numbers would be 0 after xor. the one remaining would be the answer.

• @gankzpn Great!Thank you!

• This is unbelievable. You must be a security expert..

• Btw you don't really need the first few lines. Just straightly go to the for loop will do ;)

• What a smart solution it is! Thanks!

• ported to C++

``````class Solution {
public:
int singleNumber(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
for (int i = 1; i < nums.size(); i++) nums[0] ^= nums[i];
return nums[0];
}
};
``````

• Excellent code!

• The solution is really amazing

• I think the code if(nums.length==1){} is not necessary. Because if the length of an array is 1, the loop part will not be conducted (For the first loop, i cannot satisfy 1<nums.length), and the return is still nums[0]'

• Very smart solution. Hats off to you sir!

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