LeetCode 260 - Single Number III

The problem gives an integer array nums where every value appears exactly twice, except for two numbers that appear only once. The task is to find those two unique numbers and return them in any order.

leetcodemediumarraybit-manipulation

LeetCode Problem 260

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives an integer array nums where every value appears exactly twice, except for two numbers that appear only once. The task is to find those two unique numbers and return them in any order.

In other words, the array mostly contains duplicate pairs, but there are exactly two elements that do not have matching duplicates. We must isolate and return those two values.

For example, in the array [1,2,1,3,2,5], the numbers 1 and 2 each appear twice, while 3 and 5 appear only once. Therefore, the answer is [3,5] or [5,3].

The constraints are important because they strongly influence the choice of algorithm:

  • The array length can be as large as 3 * 10^4
  • Values can be negative
  • The solution must run in linear time, O(n)
  • The solution must use constant extra space, O(1)

These requirements immediately rule out several common approaches. For example, sorting would require O(n log n) time, and using a hash map would require O(n) extra space.

The problem guarantees that:

  • Exactly two numbers appear once
  • Every other number appears exactly twice

This guarantee is critical because it enables a bit manipulation solution using XOR properties.

Several edge cases are worth considering upfront. The two unique numbers may both be negative, one may be zero, or the array may contain only two elements. The implementation must also correctly separate the two unique values even if they differ by only a single bit.

Approaches

Brute Force Approach

A straightforward solution is to count how many times each number appears. We can use a hash map where the key is the number and the value is its frequency.

We iterate through the array once to build the frequency table. Then we iterate through the map and collect the numbers whose frequency is 1.

This approach is correct because the map explicitly records how many times every number appears. Any number with count 1 must be one of the required answers.

However, this solution violates the constant space requirement because the hash map may store up to O(n) distinct numbers.

Optimal Approach Using XOR and Bit Manipulation

The key observation comes from XOR properties:

  • a ^ a = 0
  • a ^ 0 = a
  • XOR is commutative and associative

If we XOR all numbers in the array together, every duplicated number cancels itself out. The final result becomes:

x ^ y

where x and y are the two unique numbers.

Since x and y are different, their XOR result must contain at least one set bit. That set bit tells us that x and y differ at that position.

We can use this differing bit to divide the numbers into two groups:

  • Numbers with the bit set
  • Numbers with the bit unset

Because duplicate numbers are identical, both copies always go into the same group and cancel each other out again.

The two unique numbers end up in different groups, allowing us to recover them individually.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses a hash map to count frequencies
Optimal O(n) O(1) Uses XOR and bit partitioning

Algorithm Walkthrough

  1. XOR all numbers in the array together.

After this step, every duplicated number cancels itself out. The remaining value is:

xor_all = unique1 ^ unique2

Since the two unique numbers are different, xor_all is nonzero. 2. Find a bit where the two unique numbers differ.

We isolate the rightmost set bit using:

differing_bit = xor_all & (-xor_all)

This operation extracts the lowest bit that equals 1. 3. Partition the numbers into two groups.

Using differing_bit, we divide all numbers into:

  • Group A: numbers where the bit is set
  • Group B: numbers where the bit is not set

The two unique numbers must fall into different groups because they differ at this bit position. 4. XOR numbers within each group.

Duplicate numbers remain in the same group and cancel out through XOR.

After processing:

  • One group produces unique1
  • The other group produces unique2
  1. Return the two unique numbers.

Why it works

The correctness depends on XOR cancellation. Every duplicated number appears exactly twice, so XOR removes them completely. The remaining XOR value identifies a bit where the two unique numbers differ. Partitioning by that bit guarantees the two unique numbers land in separate groups, while duplicates remain together and still cancel out. Therefore, each group reduces to exactly one unique number.

Python Solution

from typing import List

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

        # XOR all numbers together
        for num in nums:
            xor_all ^= num

        # Isolate the rightmost set bit
        differing_bit = xor_all & -xor_all

        unique1 = 0
        unique2 = 0

        # Divide numbers into two groups
        for num in nums:
            if num & differing_bit:
                unique1 ^= num
            else:
                unique2 ^= num

        return [unique1, unique2]

The implementation begins by XORing every number in the array. Because duplicates cancel each other, the result becomes the XOR of only the two unique values.

Next, the code extracts the rightmost set bit using:

differing_bit = xor_all & -xor_all

This bit must differ between the two unique numbers.

The algorithm then loops through the array again and separates numbers based on whether this bit is set. Each group performs its own XOR accumulation.

Since duplicate values always enter the same group, they cancel out again. Each accumulator ultimately contains one unique number.

Finally, the solution returns both results in a list.

Go Solution

func singleNumber(nums []int) []int {
	xorAll := 0

	// XOR all numbers together
	for _, num := range nums {
		xorAll ^= num
	}

	// Isolate the rightmost set bit
	differingBit := xorAll & -xorAll

	unique1 := 0
	unique2 := 0

	// Divide numbers into two groups
	for _, num := range nums {
		if num&differingBit != 0 {
			unique1 ^= num
		} else {
			unique2 ^= num
		}
	}

	return []int{unique1, unique2}
}

The Go implementation follows the exact same logic as the Python version. Go slices are used instead of Python lists, and bit operations work directly on integers.

One small syntax difference is the conditional check:

if num&differingBit != 0

Go requires explicit comparison against zero for bitwise conditions.

Negative numbers are handled correctly because Go integers use two's complement representation, just like Python internally does for bitwise operations.

Worked Examples

Example 1

Input:

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

Step 1: XOR all numbers

Operation Result
0 ^ 1 1
1 ^ 2 3
3 ^ 1 2
2 ^ 3 1
1 ^ 2 3
3 ^ 5 6

Final value:

xor_all = 6

Binary representation:

6 = 110

Step 2: Extract rightmost set bit

differing_bit = 6 & -6 = 2

Binary:

010

Step 3: Partition numbers

Number Binary Group
1 001 unset
2 010 set
1 001 unset
3 011 set
2 010 set
5 101 unset

Step 4: XOR within groups

Set group:

2 ^ 3 ^ 2 = 3

Unset group:

1 ^ 1 ^ 5 = 5

Answer:

[3,5]

Example 2

Input:

nums = [-1,0]

XOR all numbers

-1 ^ 0 = -1

Extract differing bit

The rightmost set bit of -1 is 1.

Partition

Number Group
-1 set
0 unset

XOR groups

unique1 = -1
unique2 = 0

Answer:

[-1,0]

Example 3

Input:

nums = [0,1]

XOR all numbers

0 ^ 1 = 1

Extract differing bit

differing_bit = 1

Partition

Number Group
0 unset
1 set

XOR groups

unique1 = 1
unique2 = 0

Answer:

[1,0]

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is traversed twice
Space O(1) Only a few integer variables are used

The algorithm performs two linear passes through the array. The first computes the XOR of all elements, and the second separates numbers into groups and recovers the unique values.

No auxiliary data structures proportional to input size are used. The algorithm only stores a constant number of integer variables, satisfying the constant space requirement.

Test Cases

from typing import List

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

        for num in nums:
            xor_all ^= num

        differing_bit = xor_all & -xor_all

        unique1 = 0
        unique2 = 0

        for num in nums:
            if num & differing_bit:
                unique1 ^= num
            else:
                unique2 ^= num

        return [unique1, unique2]

sol = Solution()

# Provided examples
assert sorted(sol.singleNumber([1,2,1,3,2,5])) == [3,5]  # standard example
assert sorted(sol.singleNumber([-1,0])) == [-1,0]        # includes negative number
assert sorted(sol.singleNumber([0,1])) == [0,1]          # minimum valid size

# Additional edge cases
assert sorted(sol.singleNumber([2,1])) == [1,2]          # only two unique numbers
assert sorted(sol.singleNumber([4,1,2,1,2,5])) == [4,5] # uniques separated by duplicates
assert sorted(sol.singleNumber([-2,-2,-3,-4])) == [-4,-3] # both unique numbers negative
assert sorted(sol.singleNumber([0,0,7,8])) == [7,8]     # duplicates are zero
assert sorted(sol.singleNumber([10,14,10,20])) == [14,20] # small positive integers
assert sorted(sol.singleNumber([100,200,100,300])) == [200,300] # larger values
assert sorted(sol.singleNumber([-1,-1,-2,-3])) == [-3,-2] # negative unique values

Test Case Summary

Test Why
[1,2,1,3,2,5] Standard mixed example
[-1,0] Tests negative number handling
[0,1] Minimum input size
[2,1] Only unique numbers present
[4,1,2,1,2,5] Duplicates interleaved with uniques
[-2,-2,-3,-4] Both unique numbers negative
[0,0,7,8] Zero appears as duplicate
[10,14,10,20] Simple positive values
[100,200,100,300] Larger integers
[-1,-1,-2,-3] Negative unique values

Edge Cases

One important edge case occurs when the array contains only two elements, such as [0,1]. In this scenario, both numbers are unique and there are no duplicate pairs at all. Some implementations incorrectly assume duplicates must exist. This algorithm still works because XOR simply becomes 0 ^ 1, and the partition step cleanly separates the two numbers.

Another important case involves negative integers. Bit manipulation with negative numbers can sometimes cause confusion because of two's complement representation. For example, in [-1,0], the algorithm still correctly extracts a differing bit and partitions the numbers properly. XOR operations behave consistently for signed integers, so the implementation handles negatives without special logic.

A third edge case occurs when zero appears among the duplicated values, such as [0,0,7,8]. Since 0 ^ 0 = 0, duplicates of zero cancel out exactly like any other number. The algorithm treats zero naturally during XOR accumulation and group partitioning.

Another subtle case is when the two unique numbers differ by only a single bit. In that situation, the XOR result contains only one set bit. The expression:

xor_all & -xor_all

still correctly isolates that bit, ensuring the numbers are separated into different groups.