[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. 😉😃💗