# 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.

### Recommended Posts

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

##### Jump Game IV | LeetCode | Solution Explained

January 15, 2022