Single Number III Bit Partition DSA Solution

Learning Outcome

After this lesson, you should be able to split numbers into two XOR groups using a bit where the two answers differ.

Problem Statement

Given an integer array where exactly two elements appear once and all others appear twice, return the two single elements.

Input	Output	Why
`nums = [1,2,1,3,2,5]`	`[3,5]`	1 and 2 cancel as pairs; 3 and 5 remain as the two unique values.

Brute Force Approach

Use a frequency map and collect values with count 1. This is simple but uses extra memory.

Optimized Approach

XOR all values to get xorAll = a xor b. Pick the rightmost set bit of xorAll to separate a and b into different groups, then XOR within each group.

Exact Pseudocode

xorAll = 0
for x in nums:
  xorAll = xorAll xor x
mask = xorAll & -xorAll
a = 0
b = 0
for x in nums:
  if x & mask:
    a = a xor x
  else:
    b = b xor x
return [a, b]

Reference Code

class Solution:
    def singleNumber(self, nums):
        xor_all = 0
        for x in nums:
            xor_all ^= x

        mask = xor_all & -xor_all
        a = 0
        b = 0
        for x in nums:
            if x & mask:
                a ^= x
            else:
                b ^= x
        return [a, b]

Sample Dry Run

Step	State	Result
XOR all	duplicates cancel	xorAll = 3 xor 5
Find mask	mask is a bit where 3 and 5 differ	groups separate answers
XOR group A	duplicates inside group cancel	one answer remains
XOR group B	duplicates inside group cancel	other answer remains

Complexity

Measure	Value	Reason
Time	O(n)	The array is scanned twice.
Space	O(1)	Only xorAll, mask, and two answers are stored.

Edge Cases

The two unique values must be different, so xorAll is nonzero.
Output order usually does not matter.
Use a real differing bit, not a random bit.

Interview Checklist

XOR all values first.
Use rightmost set bit to split groups.
XOR inside each group to cancel duplicates.

FAQs

Why does the mask separate the two answers?

The mask is set in xorAll, so one answer has that bit and the other does not.

Why do duplicates stay together?

Equal numbers have the same mask bit, so each duplicate pair lands in the same group and cancels.

What is the core pattern?

XOR partition by rightmost set bit.

Single Number III: Rightmost Set Bit Pattern