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]:
        mask = 0
        for num in nums:
            mask ^= num
        # mask = x^y

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]:
        mask = 0
        for num in nums:
            mask ^= num
        
        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
        
        return [x, mask^x]

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.