Single number (use XOR):
Single number (use XOR):
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
A brief explanation of how and why your code works and how it relates to the concepts learned (for example, it uses bitwise operation, stack, or takes into account a word size).
One can easily solve this question using the naive algorithm. But the solution for O(1) extra memory is tricky. It can be solved by using properties of XOR(a bitwise operator). It is very simple to verify the following properties of XOR :
- 0 ^ a = a,
- a ^ a = 0,
- a ^ b = b ^ a
The algorithm is small but difficult to understand. Let us analyze the algorithm by using an example.
- singleNumber(const vector<int> &A) {
- int res = 0;
- for(int i=0; i<A.size(); i++)
- {
- res ^= A[i];
- }
- return res;
- }
Let us take an array a[3] = {2, 1, 2}, and res=0.
ans = res ^ 2 ^ 1 ^ 2,
=> ans = (0 ^ 2) ^ 1 ^ 2,
=> ans = 2 ^ 1 ^ 2,
=> ans = 2 ^ 2 ^ 1, (using 3rd properties stated above)
=> ans = (2 ^ 2) ^ 1,
=> ans = 0 ^ 1,
=> ans = 1
Step by step
Solved in 2 steps
