[LeetCode][136. Single Number] The XOR Cheat Sheet | Bit Manipulation with Easy Detailed Explanation

By Long Luo

This article is the solution The XOR Cheat Sheet and Bit Manipulation with Easy Detailed Explanation 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 \(0\), 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)\).
• Space Complexity: \(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. 😉😃💗