https://leetcode.com/problems/single-number/

Problem statement:

``````Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1``````

When you see these kinds of problem your first approach should always be to find a brute force solution. For this one we can use a hashtable to quickly solve this one.

Once we know we can solve this using brute-force then we start to look for optimisation. Is it possible to solve this one without using any space?

When you XOR 2 same number, what do you get? For example what is 10 ^ 10?
It's 0.
No matter what number you XOR with itself, the result will always be 0.

So, with that in mind, what is result of this? 2^1^2^3^3

Since XOR is commutative & associative:

We can write ((2^2)^(3^3)^1).

After simplifying we get 0^1 which is just 1.

## Solution[Java]:

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