Single Number | LeetCode | Bit Manipulation Solution Explained

LeetCode 136. Single Number can be solved using the idea of bits. But how to even think about it? And what to do after that? I explain the observations and intuitions for this problems. Problem Link.

0. Single Number: Problem Discussion

• Given: Array nums where there is only one element that appears with frequency 1, and the rest appear with frequency 2.
• Goal: Find the number with frequency = 1

Example: nums = [2, 2, 3, 3, 4, 4, 5] returns the number 5, since it is the only one that appears with frequency 1, the rest have duplicates.

What makes this problem non-trivial is the additional constraint on space, that it has to be O(1) only in the same linear O(N) time for a naive solution – perhaps using a dictionary to store the frequencies.

1. Single Number: Observations and Logic

1.0. How do we even think about a bit based approach?

The first thing to note is that there is a shortage of space. We want something that can deal with the nums without taking too much space. Creating anything other than a variable will not be viable. How can we store the information of the entire nums in a single variable?

This is where bits can help us. Thinking of numbers as bits can help us, since they are a compact representation of the number (only 32 bits needed to represent the entire integer range!).

1.1. What to do with bits?

Somehow, now we want these bits to be able to say whether a number is appearing twice or not. An operation on all of these numbers that can lead us to the answer.

One of the operations that you should know is the bitwise operation, XOR, represented by ^. Here are some properties of XOR:

• x^0 = x
• x^INT_MAX = ~x
• x^x = 0
• XOR is commutative: x^y = y^x
• XOR is associative: x^(y^z) = (x^y)^z

The third one holds the key to our answer. While x^0 gives x itself, when we do something like x^y^z^z^y, due to commutativity and then y^y and z^z becoming 0, x remains at the end!

So, in one line, we can XOR all the nums to find the non-repeating num.

2. Single Number: Implementation

2.0. Code

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor ^= num
        return xor

2.1. Complexity Analysis

• Time: O(N), to iterate over all the elements
• Space: O(1) as we don’t store anything else.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.