LeetCode 260: Single Number III

Problem Restatement

We are given an integer array nums.

Exactly two numbers appear only once.

Every other number appears exactly twice.

We need to return the two numbers that appear only once.

The answer may be returned in any order.

The problem asks for:

• Linear runtime
• Constant extra space

The constraints are 2 <= nums.length <= 3 * 10^4, -2^31 <= nums[i] <= 2^31 - 1. (github.com)

Input and Output

Example function shape:

def singleNumber(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [1, 2, 1, 3, 2, 5]

Numbers 1 and 2 appear twice.

Numbers 3 and 5 appear once.

Answer:

[3, 5]

Example 2:

nums = [-1, 0]

Both numbers appear once.

Answer:

[-1, 0]

Example 3:

nums = [0, 1]

Both numbers appear once.

Answer:

[0, 1]

First Thought: Count Frequencies

A direct solution uses a hash map.

Count how many times each number appears.

Then return the numbers with count 1.

class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        freq = {}

        for x in nums:
            freq[x] = freq.get(x, 0) + 1

        ans = []

        for x, count in freq.items():
            if count == 1:
                ans.append(x)

        return ans

This works, but it uses extra memory.

Problem With Hash Maps

The follow-up requires constant extra space.

A frequency table needs:

space in the worst case.

We need to exploit the structure of the problem instead.

The key observation is that every duplicated number appears exactly twice.

That strongly suggests XOR.

XOR Properties

XOR has two critical properties:

For example:

1 ^ 1 = 0
5 ^ 5 = 0

So if we XOR the entire array:

xor_all = a ^ b

all duplicated numbers disappear.

Only the two unique numbers remain.

Suppose:

a = 3
b = 5

Then:

3 ^ 5 = 6

Binary:

3 = 011
5 = 101
-----------
    110

The XOR result contains bits where a and b differ.

Key Insight

If two numbers differ at some bit position, then:

• One has bit 0
• The other has bit 1

We can use one differing bit to separate the array into two groups.

Inside each group:

• Duplicate numbers still appear twice, so they cancel out.
• The two unique numbers go into different groups.

Then XOR inside each group gives the answer.

Finding a Differing Bit

Suppose:

xor_all = a ^ b

Since a != b, at least one bit is set in xor_all.

We isolate one set bit using:

diff = xor_all & -xor_all

This extracts the rightmost set bit.

For example:

xor_all = 6 = 110
-diff representation isolates:
diff = 010

Now we partition numbers by whether this bit is set.

Algorithm

1. XOR all numbers together.
2. The result becomes:

   xor_all = a ^ b
3. Extract one differing bit:

   diff = xor_all & -xor_all
4. Partition the array into two groups:
   • Bit set
   • Bit not set
5. XOR numbers inside each group.
6. Duplicate values cancel out.
7. The remaining values are the two answers.

Walkthrough

Use:

nums = [1, 2, 1, 3, 2, 5]

Step 1: XOR Everything

Compute:

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5

Pairs cancel:

(1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 5)

Result:

0 ^ 0 ^ 6 = 6

So:

xor_all = 6

Binary:

6 = 110

Step 2: Extract One Set Bit

diff = xor_all & -xor_all

Result:

diff = 2

Binary:

010

Step 3: Partition Numbers

Group 1: bit set

2, 3, 2

Group 2: bit not set

1, 1, 5

Step 4: XOR Each Group

Group 1:

2 ^ 3 ^ 2 = 3

Group 2:

1 ^ 1 ^ 5 = 5

Answer:

[3, 5]

Correctness

Let the two unique numbers be a and b.

XORing the entire array cancels every duplicated number because:

So the total XOR becomes:

Since a != b, at least one bit in xor_all is set.

The value:

diff = xor_all & -xor_all

isolates one such differing bit.

At this bit position:

• One of a and b has bit 1
• The other has bit 0

Therefore a and b are placed into different groups.

Every duplicated number appears twice with identical bits, so both copies enter the same group and cancel under XOR.

After XORing each group separately, only the unique number from that group remains.

Thus the algorithm returns exactly the two numbers appearing once.

Complexity

Implementation

class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        xor_all = 0

        for x in nums:
            xor_all ^= x

        diff = xor_all & -xor_all

        a = 0
        b = 0

        for x in nums:
            if x & diff:
                a ^= x
            else:
                b ^= x

        return [a, b]

Code Explanation

First compute the XOR of the full array:

xor_all ^= x

All duplicated values cancel out.

The result becomes:

a ^ b

Next isolate one differing bit:

diff = xor_all & -xor_all

This bit separates the two unique numbers.

We create two XOR accumulators:

a = 0
b = 0

Then partition numbers using the extracted bit:

if x & diff:

Numbers with the bit set go into one group.

Others go into the second group.

Inside each group, duplicates cancel, leaving exactly one unique number.

Finally return both results.

Testing

def normalize(ans: list[int]) -> list[int]:
    return sorted(ans)

def run_tests():
    s = Solution()

    assert normalize(s.singleNumber([1, 2, 1, 3, 2, 5])) == [3, 5]
    assert normalize(s.singleNumber([-1, 0])) == [-1, 0]
    assert normalize(s.singleNumber([0, 1])) == [0, 1]
    assert normalize(s.singleNumber([4, 1, 2, 1, 2, 5])) == [4, 5]
    assert normalize(s.singleNumber([7, 7, 8, 9])) == [8, 9]
    assert normalize(s.singleNumber([-3, -3, -1, -2])) == [-2, -1]

    print("all tests passed")

run_tests()

Test meaning: