Problem statement:

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


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.


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