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