# Single Number III | LeetCode | Bit Manipulation Solution Explained

LeetCode 260. Single Number III. I explain the bit-masking solution in detail, with the help of some neat observations. Problem Link.

## 0. Single Number: Problem Discussion

• Given: An array of integers, nums, `-231 <= nums[i] <= 231 - 1`
• Goal: Find two numbers that appear only once, given all others appear twice.

The problem Single Number III can be thought of as an extension to the problem Single Number I, where instead of two numbers with frequency 1, there is only one. Problem Link: Single Number I.

I’d highly recommend reading Single Number | LeetCode | Bits Based Solution Explained. It explains how to even think about bits and how to approach this problem. We are going to use the bits to make sense of the solution.

## 1. Single Number: Observations & Logic

### 1.0. Stuck after Single Number I?

As we saw in the Single Number | LeetCode | Bits Based Solution Explained, we xor all the elements together, and the non-repeating num pops out. Things aren’t that easy here, since the xor at the end of this `nums` would be xor of `x` and `y`, the two numbers we want to return.

```class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
for num in nums:

### 1.1. Putting the bits together

Since x and y are different (by definition), what can we say about their binary representations? At least 1 bit will be different between both x and y. Let’s call it `diff`. We can find it using the code segment below:

```        diff = None
for diff in range(0, 33):
if (1 << diff) & mask: break```

Here’s the fun observation: all the num in nums having a `diff` bit set are in duplicates, except, for ONE of the numbers, which is the number x.

Wait what?

In the case above, XOR was 010. This means that the numbers x and y have differing bits in the 1 position. Alternatively, if we filter out all the numbers having the bit set in 1 position, we get: [2, 3, 2, 3, 7].

We have effectively converted the problem Single Number III into Single Number I!

## 2. Single Number: Implementation

### 2.0. Code

```class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
for num in nums:

diff = None
for diff in range(0, 33):
if (1 << diff) & mask: break

x = 0
for num in nums:
if (1 << diff) & num:
x ^= num

```

### 2.1. Complexity Analysis

• Time: O(N), to iterate over all the elements
• Space: O(1), to store mask, diff, x.
##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Seats | InterviewBit | Solution Explained

June 13, 2022

1. bipbop :September 13, 2023 at 12:30 pm