Single Number III

Single Number III

What is this problem about?

The "Single Number III" interview question takes the difficulty even further. In an array, every element appears twice, except for two elements that appear only once. Your goal is to find both unique elements in O(n) time and O(1) space. This "Single Number III coding problem" requires a clever combination of the XOR trick and a technique to partition the array into two manageable groups.

Why is this asked in interviews?

This is a favorite at companies like Microsoft and Google because it requires "two-stage" thinking. First, you use a known trick (XOR), and then you have to creatively solve the problem of separating the two unique numbers. It evaluates your ability to build upon existing knowledge to solve more complex problems, a core skill in software engineering.

Algorithmic pattern used

This problem uses the "Bit Manipulation and Partitioning interview pattern".

1. XOR all numbers. The result X is the XOR of the two unique numbers a ^ b.
2. Since a and b are different, X must have at least one bit set (let's say the k-th bit).
3. This k-th bit exists because a and b differ at that position.
4. Partition the entire array into two groups: those with the k-th bit set and those without.
5. a will fall into one group, and b into the other. All other pairs will also be split into the groups but will cancel out within their respective groups during a second XOR pass. Each group's final XOR result will be one of the two unique numbers.

Example explanation

Array: [1, 2, 1, 3, 2, 5]

1. XOR all: 1^2^1^3^2^5 = 3 ^ 5 = 6 (binary 110).
2. Pick a set bit in 6: The second bit (value 2, binary 010) is set.
3. Partition:
   • Group 1 (bit 1 is 1): [2, 3, 2] -> XOR sum is 3.
   • Group 2 (bit 1 is 0): [1, 1, 5] -> XOR sum is 5. Unique numbers are 3 and 5.

Common mistakes candidates make

A common mistake is failing to correctly find the "rightmost set bit" to use as a partition criteria (the trick X & -X is very useful here). Some candidates also struggle to explain why partitioning works, especially how the pairs are guaranteed to be split such that they cancel out. Like previous variations, using a Hash Map is often discouraged because it uses O(n) space, which isn't allowed in the "Single Number III interview question".

Interview preparation tip

The trick n & -n isolates the rightmost set bit of a number. This is a very common bitwise utility that appears in many "HARD" level bit manipulation problems and competitive programming. Adding this to your "Interview preparation tip" list will help you solve problems involving bitmasks and low-level optimizations more efficiently.