[Leetcode][136. Single Number] 5 Lines Code | The XOR operator Cheatsheet | Bit Manipulation with Easy Detailed Explanation

By Long Luo

This article is the solution of Problem 136. Single Number.

To solve this problem, there are serval solutions. However, the best method is using XOR.

we have this XOR cheatsheet:

1
2
3
4
5
1.  Zero Law: a XOR a = 0
2. a XOR 0 = a
3. a XOR b = b XOR a
4. a XOR b XOR c = a XOR (b XOR c) = (a XOR b) XOR c
5. a XOR b XOR a = b

According to the Zero law, all the numbers appears twice will be 00, and the single one will remain.

So code as follow:

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
}

Analysis

  • Time Complexity: O(n)O(n).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗