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
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.
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
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.
January 24, 2022
January 20, 2022
January 15, 2022