Xor Patterns - Learning Module

Loading content...

0/279

Find Two Single Numbers

When One XOR Isn't Enough

The single-number problem was elegant: XOR everything, and the unique element remains. But what if two elements each appear exactly once? XORing everything gives us A ⊕ B—a combination of both unique elements that we cannot trivially separate.

This problem seems to require O(n) space... until you discover a brilliant insight that extends the XOR technique. By using a distinguishing bit to partition the array, we can reduce this problem to two instances of the single-number problem.

This is one of the most beautiful bit manipulation algorithms—and a favorite among interviewers for senior positions.

What You Will Learn

By the end of this page, you will understand the two-phase approach (XOR all, then partition), implement the solution in O(n) time and O(1) space, and recognize how to extend bit manipulation techniques to more complex problems.

Problem Formalization

Problem Statement:

Given an array of integers where every element appears exactly twice except for two elements which appear exactly once, find those two elements.

Constraints:

2 ≤ nums.length ≤ 3 × 10⁴
Each element appears exactly twice except for two elements which appear only once
The two unique elements are distinct from each other

Requirements:

Time Complexity: O(n)
Space Complexity: O(1)

Examples:

Example Inputs and Outputs
Input Array	Output (either order)	Explanation
[1, 2, 1, 3, 2, 5]	[3, 5] or [5, 3]	3 and 5 appear once each
[0, 1]	[0, 1]	Both elements are unique
[-1, 0]	[-1, 0]	Works with negative and zero
[1, 1, 2, 2, 3, 4]	[3, 4]	Multiple duplicates

Key Difference from Single Number

Unlike the single-number problem, we cannot directly use XOR to get the answer. XORing all elements gives us A ⊕ B, where A and B are the two unique elements. We need an additional technique to separate them.

Why Simple XOR Fails

Let's trace through the naive XOR approach to see exactly why it doesn't work directly.

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

XOR of all elements:
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 5)  [regroup]
= 0 ^ 0 ^ (3 ^ 5)              [duplicates cancel]
= 3 ^ 5                         [identity]
= 6                             [compute XOR]

The Result: We get 6, which is 3 ^ 5. Both unique elements are "encoded" together in this result. But how do we recover 3 and 5 individually from 6?

The Challenge:

6 = 110 in binary
3 = 011 in binary
5 = 101 in binary

The XOR result tells us where A and B differ, but not what A and B actually are.

The Key Insight

Since A ≠ B, the value A ⊕ B is non-zero. This means at least one bit position is different between A and B. We can use this differing bit to partition the entire array into two groups: one containing A, and one containing B.

The Distinguishing Bit Strategy

Here's the brilliant insight that makes this problem solvable in O(1) space:

Observation 1: Since A ≠ B, at least one bit differs between them. Let's call this the distinguishing bit.

Observation 2: If we partition all numbers by whether they have this bit set:

A goes into one group, B goes into the other (they differ at this bit)
Each duplicate pair goes into the same group (identical numbers have identical bits)

Observation 3: Within each group, we now have the single-number problem:

Group 1: Contains A and all duplicates with this bit set
Group 2: Contains B and all duplicates with this bit unset

We can XOR each group separately to find A and B!

How to Find a Distinguishing Bit:

The XOR of all elements (A ⊕ B) has 1's exactly where A and B differ. We can use any of these 1-bits. The easiest to find is the rightmost set bit, which can be extracted with:

diff_bit = xor_all & (-xor_all)

Or equivalently:

diff_bit = xor_all & ~(xor_all - 1)

Visualizing the Distinguishing Bit
Value	Binary	Has Bit 1 Set?	Group
1	001	Yes	Group A
2	010	No	Group B
1	001	Yes	Group A
3	011	Yes	Group A
2	010	No	Group B
5	101	Yes	Group A

Continuing the Example:

With distinguishing bit = 2 (binary 010):

Group A (bit 1 NOT set): [2, 2] → XOR = 0. But wait, let's use a different bit!

Actually, let's use the rightmost set bit of 6 (110), which is 2 (010):

Wait, 3 = 011 has bit 1 set. 5 = 101 does not. Let's re-partition.

Using bit position 1 (value 2):

Has bit: 3 (011), 2 (010), 2 (010) → XOR = 3
Doesn't have bit: 1 (001), 1 (001), 5 (101) → XOR = 5

Perfect! We recovered both unique elements.

Complete Algorithm

Let's formalize the complete algorithm:

Step 1: XOR all elements to get xor_all = A ⊕ B

Step 2: Find a distinguishing bit (any bit that is 1 in xor_all)

Formula: diff_bit = xor_all & (-xor_all) gives the rightmost set bit

Step 3: Partition and XOR

Partition all elements into two groups based on the distinguishing bit
XOR elements in each group separately
One group yields A, the other yields B

Time Complexity: O(n) — two passes through the array Space Complexity: O(1) — only a few integer variables

two_single_numbers.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def find_two_single_numbers(nums: list[int]) -> list[int]:
    """
    Find two elements that appear exactly once.
    All other elements appear exactly twice.
    
    Time Complexity: O(n) - two passes through array
    Space Complexity: O(1) - constant extra space
    
    Algorithm:
    1. XOR all elements to get xor_all = A ^ B
    2. Find a bit where A and B differ (distinguishing bit)
    3. Partition elements by this bit and XOR each partition
    """
    
    # Step 1: XOR all elements to get A ^ B
    xor_all = 0
    for num in nums:
        xor_all ^= num
    
    # Step 2: Find a distinguishing bit (rightmost set bit)
    # Since A != B, xor_all has at least one bit set
    # Formula: x & (-x) isolates the rightmost set bit
    diff_bit = xor_all & (-xor_all)
    
    # Step 3: Partition and XOR
    a = 0  # Will hold one unique number
    b = 0  # Will hold the other unique number
    
    for num in nums:
        if num & diff_bit:
            # This number has the distinguishing bit set
            a ^= num
        else:
            # This number does not have the distinguishing bit set
            b ^= num
    
    return [a, b]
 
 
# Test cases
test_cases = [
    [1, 2, 1, 3, 2, 5],  # Expected: {3, 5}
    [0, 1],              # Expected: {0, 1}
    [-1, 0],             # Expected: {-1, 0}
    [1, 1, 2, 2, 3, 4],  # Expected: {3, 4}
    [2, 3],              # Expected: {2, 3}
]
 
print("Testing find_two_single_numbers:")
for nums in test_cases:
    result = find_two_single_numbers(nums)
    print(f"  {nums} → {result}")

Step-by-Step Execution Trace

Let's trace through the algorithm with the example [1, 2, 1, 3, 2, 5] where 3 and 5 are the unique elements.

Step 1: XOR All Elements

Phase 1: Computing xor_all
Element	xor_all (before)	Operation	xor_all (after)	Binary
1	0	0 ^ 1	1	001
2	1	1 ^ 2	3	011
1	3	3 ^ 1	2	010
3	2	2 ^ 3	1	001
2	1	1 ^ 2	3	011
5	3	3 ^ 5	6	110

Result: xor_all = 6 (binary: 110)

This is 3 ^ 5 = 011 ^ 101 = 110.

Step 2: Find Distinguishing Bit

diff_bit = xor_all & (-xor_all)
         = 6 & (-6)
         = 110 & 010  (in binary, -6 in two's complement has rightmost 010 pattern)
         = 010
         = 2

The distinguishing bit is 2 (bit position 1). At this bit position, 3 and 5 differ:

3 = 011 → bit 1 is 1
5 = 101 → bit 1 is 0

Step 3: Partition and XOR

Phase 2: Partitioning by Distinguishing Bit (value 2)
Element	Binary	Bit 1	Group	Running XOR
1	001	0	b group	b = 0 ^ 1 = 1
2	010	1	a group	a = 0 ^ 2 = 2
1	001	0	b group	b = 1 ^ 1 = 0
3	011	1	a group	a = 2 ^ 3 = 1
2	010	1	a group	a = 1 ^ 2 = 3
5	101	0	b group	b = 0 ^ 5 = 5

Final Result: a = 3, b = 5

Verification:

a group: [2, 2, 3] → 2 ^ 2 ^ 3 = 3 ✓
b group: [1, 1, 5] → 1 ^ 1 ^ 5 = 5 ✓

The duplicates cancelled within each partition, leaving the unique elements!

Why the Partitioning Works — Rigorous Proof

Let's prove that the partitioning strategy always correctly separates A and B.

Theorem: Given an array where elements A and B appear once each, and all other elements appear twice, partitioning by any bit where A and B differ will put A in one group and B in the other, with all duplicates properly paired within groups.

Proof:

Part 1: A and B are separated

Let d be a bit where A and B differ. WLOG assume A has bit d set and B does not.

A goes to group_with_d (has the bit)
B goes to group_without_d (lacks the bit)

A and B are guaranteed to be in different groups.

Part 2: Duplicates stay together

For any element X appearing twice:

Both copies of X have identical bits (they're the same number)
Both copies go to the same group (same bit pattern)
In that group, X ^ X = 0 (self-cancellation)

Duplicates always pair up and cancel within their group.

Part 3: Final XOR yields unique elements

After all elements are processed:

Group with A: (duplicate pairs) ^ A = 0 ^ A = A
Group with B: (duplicate pairs) ^ B = 0 ^ B = B

QED: The algorithm always correctly finds A and B.

Any Differing Bit Works

We use the rightmost set bit for convenience (easy to compute), but any bit that is 1 in xor_all would work. All such bits represent positions where A and B differ, so any of them can serve as the distinguishing bit.

Handling Edge Cases

The algorithm handles several edge cases correctly, but some deserve special attention.

Edge Case 1: One Element is Zero

Input: [0, 1, 1, 5]
xor_all = 0 ^ 1 ^ 1 ^ 5 = 5
diff_bit = 5 & (-5) = 1

Partition:
  Bit 0 set: [1, 1, 5] → 1 ^ 1 ^ 5 = 5
  Bit 0 not set: [0] → 0

Result: [5, 0] ✓

Zero is handled correctly because it still has a well-defined bit pattern (all zeros).

Edge Case 2: Negative Numbers

Input: [-3, 5, 5, -7]
This works because XOR operates on bit patterns.
Negative numbers in two's complement have well-defined XOR behavior.

Edge Case 3: Minimum Array Size

Input: [3, 5]  // Two unique elements, no duplicates
xor_all = 3 ^ 5 = 6
diff_bit = 2

Partition:
  Has bit: [3] → 3
  Lacks bit: [5] → 5

Result: [3, 5] ✓

edge_cases_two.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def find_two_single_numbers(nums: list[int]) -> list[int]:
    # XOR all
    xor_all = 0
    for num in nums:
        xor_all ^= num
    
    # Find distinguishing bit
    diff_bit = xor_all & (-xor_all)
    
    # Partition and XOR
    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
    
    return [a, b]
 
 
# Comprehensive edge case testing
edge_cases = [
    # Zero as unique element
    {"input": [0, 1, 1, 5], "expected": {0, 5}},
    {"input": [0, 0, 3, 7], "expected": {3, 7}},
    
    # Negative numbers
    {"input": [-3, 5, 5, -7], "expected": {-3, -7}},
    {"input": [-1, -1, -2, -3], "expected": {-2, -3}},
    
    # Mix of positive and negative
    {"input": [-5, 5], "expected": {-5, 5}},
    
    # Minimum size
    {"input": [1, 2], "expected": {1, 2}},
    
    # Large values
    {"input": [2**30, 2**30, 2**29, 2**28], "expected": {2**29, 2**28}},
    
    # Sequential with gap
    {"input": [1, 2, 3, 1, 2, 5], "expected": {3, 5}},
]
 
print("Edge Case Testing:")
print("=" * 60)
for case in edge_cases:
    result = set(find_two_single_numbers(case["input"]))
    status = "✓" if result == case["expected"] else "✗"
    print(f"{status} Input: {case['input']}")
    print(f"  Result: {result}, Expected: {case['expected']}")

Integer Overflow Caution

In languages with fixed-width integers (Java, C++), be aware of edge cases with Integer.MIN_VALUE. The expression x & (-x) with x = Integer.MIN_VALUE returns Integer.MIN_VALUE, which still works for partitioning but may cause confusion. Python avoids this with arbitrary-precision integers.

Why This is O(1) Space

It's important to understand why this algorithm achieves constant space when the naive approach requires O(n) space.

Naive Approach (O(n) space):

def naive_two_singles(nums):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    return [n for n, c in count.items() if c == 1]

This uses a hash map storing up to n/2 distinct elements.

XOR Approach Variables:

Variable	Size	Purpose
xor_all	O(1)	Holds XOR of all elements
diff_bit	O(1)	The distinguishing bit mask
a	O(1)	Accumulates XOR for group 1
b	O(1)	Accumulates XOR for group 2
loop var	O(1)	Iteration variable

Total: 5 integer variables = O(1) regardless of input size.

Key Insight: XOR compresses information. The entire array's "parity signature" fits in a fixed number of bits. We don't need to remember which elements we've seen—just the cumulative XOR.

The Power of XOR Compression

XOR is a form of lossy compression. By XORing elements, we lose information about individual values but retain enough to solve the detection problem. This is why XOR-based algorithms achieve O(1) space for problems that seem to inherently require tracking all elements.

Interview Approach

This problem is harder than the single-number version and often appears in senior interviews. Here's how to present it:

Phase 1: Recognize the Challenge (1 minute)

"The single-number XOR trick gives us A ⊕ B, but we need A and B separately. The key insight is that since A ≠ B, their XOR has at least one bit set—a bit where they differ."

Phase 2: Explain the Strategy (2 minutes)

"I can use this differing bit to partition all numbers into two groups. A and B will be in different groups because they differ at this bit. Duplicates will pair up within groups because identical numbers have identical bits. Then each group is a single-number problem!"

Phase 3: Code the Solution (3-4 minutes)

Write clean code, explaining as you go.

Phase 4: Trace Through Example (2 minutes)

Walk through a small example showing both phases.

Phase 5: Analyze Complexity (1 minute)

"Two passes through the array: O(n). Five integer variables: O(1) space."

What Interviewers Look For

•Understanding of XOR properties — Can you explain why duplicates cancel?
•The partition insight — Did you discover or know the key technique?
•Clean implementation — Is the code bug-free and readable?
•Bit manipulation fluency — Can you explain x & (-x)?
•Edge case awareness — What about zero, negatives, minimum arrays?

What About Three or More Unique Elements?

A natural question is: can we extend this to three or more unique elements?

Short Answer: Not with pure XOR.

Why Two Works But Three Doesn't:

With two unique elements (A and B):

A ⊕ B gives us something non-zero
A single distinguishing bit partitions them

With three unique elements (A, B, C):

A ⊕ B ⊕ C gives us a combined value
A single bit might put two elements in the same group
We'd need multiple bits to fully separate them

Alternative for Three Elements:

The problem "Single Number II" (every element appears 3 times except one) uses a different technique: tracking bit counts modulo 3 using two variables. This is a fundamentally different approach.

General Principle:

XOR-based techniques work when:

We need to find elements appearing an odd number of times
We can partition using differing bits to reduce to simpler subproblems

For more complex occurrence patterns (e.g., one appears once, others appear 3 times), different bit-counting techniques are needed.

Beyond This Module

Problems like "Single Number II" and "Single Number III" are classic interview questions that build on XOR foundations but require additional techniques. The key is recognizing that XOR handles parity (odd/even), so different occurrence counts need counting-based approaches.

Summary

Key Takeaways

•XOR all elements gives A ⊕ B, which encodes both unique elements but doesn't separate them
•The distinguishing bit is any bit that differs between A and B (any 1-bit in A ⊕ B)
•Use x & (-x) to extract the rightmost set bit efficiently
•Partitioning by the distinguishing bit separates A and B while keeping duplicates paired
•XOR each partition reduces to two single-number problems, yielding A and B
•Complexity: O(n) time, O(1) space — optimal for this problem
•Proof of correctness: A and B differ at the chosen bit; duplicates don't

What's Next:

We've covered finding one and two unique elements. The next page explores another classic XOR application: Finding a Missing Number in a Sequence. This problem uses a clever combination of XOR with index values to achieve O(1) space.

Page Complete

You've mastered the two-unique-elements problem, one of the most elegant bit manipulation algorithms. This partitioning strategy—using a differing bit to reduce complexity—is a powerful technique that appears in many advanced algorithms.