XOR Patterns - Learning Module

Loading content...

0/276

Find the Single Non-Duplicate Number

The Classic XOR Interview Problem

Among all bit manipulation interview questions, one stands above the rest in elegance and frequency: Find the Single Number. This problem appears on virtually every interview preparation platform, is asked at companies from startups to FAANG, and serves as the gateway to understanding XOR-based algorithms.

The problem is deceptively simple: given an array where every element appears exactly twice except for one element that appears exactly once, find that single element. With the XOR knowledge from the previous page, you can now solve this in O(n) time with O(1) space—a feat impossible with traditional approaches.

What You Will Learn

By the end of this page, you will be able to implement the single-number finder in multiple languages, handle edge cases correctly, explain the solution to an interviewer with confidence, and recognize variations of this problem in the wild.

Problem Formalization

Let's formalize the problem precisely before diving into the solution.

Problem Statement:

Given a non-empty array of integers nums, every element appears exactly twice except for one element which appears exactly once. Find that single element.

Constraints:

1 ≤ nums.length ≤ 3 × 10⁴ (or larger in some variants)
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
Each element appears exactly twice except for one element which appears only once

Requirements:

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

Examples:

Example Inputs and Outputs
Input Array	Expected Output	Explanation
[2, 2, 1]	1	2 appears twice, 1 appears once
[4, 1, 2, 1, 2]	4	1 and 2 appear twice, 4 appears once
[1]	1	Array with single element
[-1, 1, 1]	-1	Works with negative numbers
[0, 1, 0]	1	Works with zero

Problem Guarantee

The problem guarantees exactly one element appears once. Without this guarantee, our XOR approach would still work but the interpretation would differ: the result would be the XOR of all elements appearing an odd number of times.

The XOR Solution

The solution leverages the self-cancellation property of XOR that we explored in the previous page. The algorithm is remarkably simple:

Initialize a result variable to 0
XOR every element in the array with the result
Return the result

Why does this work?

Elements appearing twice XOR themselves to 0 (A ⊕ A = 0)
XOR with 0 leaves the single element unchanged (A ⊕ 0 = A)
Due to commutativity and associativity, the order doesn't matter

single_number.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
def find_single_number(nums: list[int]) -> int:
    """
    Find the element that appears exactly once.
    All other elements appear exactly twice.
    
    Time Complexity: O(n) - single pass through array
    Space Complexity: O(1) - only one integer variable
    
    Args:
        nums: Non-empty list where exactly one element appears once
        
    Returns:
        The element that appears exactly once
    """
    result = 0
    
    for num in nums:
        result ^= num
    
    return result
 
 
# Alternative: Using functools.reduce for a more functional style
from functools import reduce
from operator import xor
 
def find_single_number_functional(nums: list[int]) -> int:
    """Functional approach using reduce and XOR operator."""
    return reduce(xor, nums)
 
 
# Test cases
test_cases = [
    ([2, 2, 1], 1),
    ([4, 1, 2, 1, 2], 4),
    ([1], 1),
    ([-1, 1, 1], -1),
    ([0, 1, 0], 1),
    ([99, 50, 50, 99, 42], 42),
]
 
print("Testing find_single_number:")
for nums, expected in test_cases:
    result = find_single_number(nums)
    status = "✓" if result == expected else "✗"
    print(f"  {status} {nums} → {result} (expected {expected})")

Step-by-Step Execution Trace

Let's trace through the algorithm with a concrete example to build intuition. Consider the array [4, 1, 2, 1, 2].

Execution Trace for [4, 1, 2, 1, 2]
Step	Current Num	result (before)	Operation	result (after)	Binary Form
Init			result = 0	0	000
1	4	0	0 ^ 4	4	100
2	1	4	4 ^ 1	5	101
3	2	5	5 ^ 2	7	111
4	1	7	7 ^ 1	6	110
5	2	6	6 ^ 2	4	100

Observation: The final result is 4, which is the single element.

Mathematical Verification:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)   [regroup by commutativity & associativity]
= 4 ^ 0 ^ 0               [self-cancellation]
= 4                       [identity]

The order of operations doesn't matter—we could have processed the array backwards, randomly, or in any order, and the result would be the same.

Interview Tip

When explaining this solution in an interview, walk through a small example showing the regrouping and cancellation. This demonstrates deep understanding rather than just memorization of the technique.

Edge Cases and Robustness

Robust implementations handle edge cases gracefully. Let's examine each edge case and verify our solution works correctly.

Edge Case 1: Single-Element Array

Input: [5]
Process: 0 ^ 5 = 5
Output: 5 ✓

With only one element, there's nothing to cancel. The single element is returned directly.

Edge Case 2: Negative Numbers

Input: [-3, 1, -3]
Process: 0 ^ (-3) ^ 1 ^ (-3) = 0 ^ 1 = 1
Output: 1 ✓

XOR works on the binary representation. Negative numbers in two's complement still XOR correctly because identical bit patterns cancel.

Edge Case 3: Zero as the Single Element

Input: [0, 7, 7]
Process: 0 ^ 0 ^ 7 ^ 7 = 0
Output: 0 ✓

Zero doesn't break XOR. In fact, XOR with 0 is the identity operation.

Edge Case 4: Large Numbers

Input: [2147483647, -2147483648, -2147483648]
Process: Works correctly at bit level
Output: 2147483647 ✓

XOR operates bit-by-bit, so large numbers don't cause overflow issues.

edge_cases.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
def find_single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result
 
 
# Comprehensive edge case testing
edge_cases = [
    # Single element
    {"input": [42], "expected": 42, "desc": "Single element array"},
    
    # Negative numbers
    {"input": [-5, 3, 3], "expected": -5, "desc": "Negative single"},
    {"input": [-5, -3, -3], "expected": -5, "desc": "All negative"},
    
    # Zero handling
    {"input": [0, 1, 1], "expected": 0, "desc": "Zero is the single"},
    {"input": [0, 0, 5], "expected": 5, "desc": "Zero as duplicate"},
    
    # Large numbers  
    {"input": [2**30, 1, 1], "expected": 2**30, "desc": "Large positive"},
    {"input": [-2**31, -2**31, 100], "expected": 100, 
     "desc": "Extreme negative as duplicate"},
    
    # Same element three times (odd count)
    {"input": [7, 7, 7], "expected": 7, "desc": "Same element 3x (odd)"},
    
    # Interleaved duplicates
    {"input": [1, 2, 3, 2, 3, 1, 4], "expected": 4, 
     "desc": "Interleaved pattern"},
]
 
print("Edge Case Testing:")
print("=" * 60)
for case in edge_cases:
    result = find_single_number(case["input"])
    status = "✓" if result == case["expected"] else "✗"
    print(f"{status} {case['desc']}")
    print(f"  Input: {case['input']}")
    print(f"  Output: {result} (expected: {case['expected']})")
    print()

Important Assumption

The XOR solution assumes the problem constraints are satisfied (exactly one element appears once, all others exactly twice). If these constraints are violated, the algorithm still runs but the result may be meaningless. In production, consider adding validation if the input source is untrusted.

Complexity Analysis

Let's rigorously analyze the time and space complexity of the XOR solution.

Time Complexity: O(n)

We iterate through the array exactly once
Each XOR operation is O(1) — it's a single CPU instruction
Total: n iterations × O(1) per iteration = O(n)

Space Complexity: O(1)

We use a single integer variable result
No additional data structures
No recursion (no stack space)
The input array is not modified

Comparison with Alternatives:

Complexity Comparison
Approach	Time	Space	Notes
XOR	O(n)	O(1)	Optimal in both dimensions
Hash Map	O(n)	O(n)	Fast but uses linear space
Sorting	O(n log n)	O(1)*	*O(n) if sort creates copy
Nested Loop	O(n²)	O(1)	For each element, count occurrences

Why XOR Achieves Optimal Bounds:

Lower bound on time: Any algorithm must examine each element at least once, so Ω(n) is required. XOR achieves this.
Lower bound on space: We only need to output a single number. XOR uses only the space for that output variable.

The XOR solution is asymptotically optimal—no algorithm can do better in terms of time or space complexity for this problem.

Practical Performance

Beyond asymptotic analysis, XOR is extremely fast in practice. It's a single CPU instruction that typically executes in 1 clock cycle. There's no function call overhead, no memory allocation, and excellent cache behavior due to sequential array access.

Common Mistakes and Pitfalls

Even with a simple algorithm, there are pitfalls to avoid. Here are common mistakes developers make when implementing or explaining the XOR solution:

Mistake 1: Forgetting to Initialize to Zero

mistake_1.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# WRONG: Initializing with the first element
def wrong_approach(nums: list[int]) -> int:
    result = nums[0]  # Bug: skips the first element!
    for num in nums:
        result ^= num
    return result
 
# This XORs nums[0] twice, canceling it out
# wrong_approach([4, 1, 2, 1, 2]) returns 0, not 4
 
# CORRECT: Initialize to 0
def correct_approach(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

Mistake 2: Missing the Mathematical Foundation

Some developers memorize "XOR everything" without understanding why. When asked to explain or modify the solution, they struggle.

Always be able to explain:

Why XOR of identical values is 0
Why order doesn't matter (commutativity + associativity)
When the technique does and doesn't apply

Mistake 3: Assuming the Input is Valid

In production code, consider what happens if constraints are violated:

Empty array: XOR of nothing is 0 (might be valid or an error)
All elements appear twice: Result is 0 (no single element)
Multiple elements appear once: Result is XOR of all such elements

robust_implementation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_single_number_robust(nums: list[int]) -> int:
    """
    Robust implementation with input validation.
    Raises appropriate errors for invalid inputs.
    """
    if not nums:
        raise ValueError("Input array cannot be empty")
    
    if len(nums) % 2 == 0:
        raise ValueError(
            "Array length must be odd for exactly one single element"
        )
    
    result = 0
    for num in nums:
        result ^= num
    
    return result
 
 
# For interview settings, the simpler version is usually preferred
# as constraints are guaranteed. But discuss robustness if asked.

Alternative Ways to Write the Solution

The core algorithm is the same, but different programming paradigms offer various ways to express it. Each style has its place.

Style 1: Traditional Loop (Most Common)

result = 0
for num in nums:
    result ^= num
return result

Pros: Clear, readable, works in all languages

Style 2: Functional with Reduce

from functools import reduce
from operator import xor
return reduce(xor, nums)

Pros: Concise, expresses intent clearly Cons: Slightly less familiar to some developers

Style 3: Using Assignment Expression (Python 3.8+)

result = 0
for num in nums: result ^= num  # One-liner with side effect

Generally not recommended—sacrifices clarity for brevity.

Style 4: Recursive (For Educational Purposes)

recursive_xor.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
def find_single_recursive(nums: list[int], index: int = 0, acc: int = 0) -> int:
    """
    Recursive implementation for educational purposes.
    Not recommended for production due to stack depth limits.
    
    Time: O(n), Space: O(n) due to recursion stack
    """
    if index >= len(nums):
        return acc
    return find_single_recursive(nums, index + 1, acc ^ nums[index])
 
 
# Tail-recursive version (Python doesn't optimize tail calls, but other languages do)
def find_single_recursive_tail(nums: list[int]) -> int:
    def helper(idx: int, acc: int) -> int:
        if idx >= len(nums):
            return acc
        return helper(idx + 1, acc ^ nums[idx])
    return helper(0, 0)
 
 
# In languages with tail call optimization (Scheme, Scala, Kotlin),
# the recursive version would use O(1) stack space.
# In Python/Java/JavaScript, stick with iteration.

Interview Advice

In interviews, use the simple loop version. It's universally understood, easy to debug, and shows you can write clean, efficient code. Save functional styles for code reviews or when the interviewer specifically asks for alternatives.

Real-World Applications

The single-number problem isn't just an interview curiosity—it has practical applications in systems and data engineering.

Application 1: Data Integrity Verification

When transferring data in pairs (e.g., request/response, write/acknowledgment), XOR can detect orphaned entries:

# Each request ID should have exactly one matching response ID
# If data is corrupted and one response is lost, XOR reveals which
all_ids = request_ids + response_ids
orphan = reduce(xor, all_ids)  # Non-zero means unpaired ID exists

Application 2: Checksum and Error Detection

XOR is used in simple checksums (like parity bits) and is the foundation of more sophisticated error-correcting codes.

Application 3: Finding Corrupted Data

In backup systems where data is stored redundantly:

# Original data + backup should have everything twice
# If one copy is corrupted, XORing all pieces reveals the difference

Application 4: Database Reconciliation

When synchronizing databases, XOR can quickly identify records that exist in one but not the other (assuming record IDs).

Industries Using XOR-Based Techniques

•Networking: Parity bits in error-correcting codes, RAID storage
•Cryptography: Stream ciphers, one-time pads (XOR with key)
•Databases: Quick reconciliation of distributed replicas
•Telecommunications: Error detection in data transmission
•File Systems: Content-addressable storage deduplication

Interview Walkthrough

Let's walk through how to present this solution in a technical interview, including the thought process and discussion points an interviewer would expect.

Step 1: Clarify the Problem (1-2 minutes)

"So I need to find the element that appears exactly once. A few clarifying questions:

Are negative numbers possible? (Usually yes)
Can zero appear in the array? (Usually yes)
Is the array guaranteed to have exactly one such element? (Usually yes)
What's the size constraint? (Determines if O(n log n) is acceptable)"

Step 2: Discuss Approaches (2-3 minutes)

"I can think of a few approaches:

1. Hash Map: Count occurrences, find element with count 1. O(n) time, O(n) space.

2. Sorting: Sort and find element not equal to its neighbor. O(n log n) time.

3. XOR: Leverage the self-cancellation property. O(n) time, O(1) space.

The XOR approach is optimal because..."

Step 3: Explain the XOR Property (1-2 minutes)

"XOR has a self-inverse property: any number XORed with itself equals 0. Also, XOR is commutative and associative, so order doesn't matter. When I XOR all elements, duplicates cancel out, leaving only the single element."

Step 4: Write the Code (2-3 minutes)

Write clean, correct code. Talk through what you're writing.

Step 5: Trace Through an Example (1-2 minutes)

Walk through [2, 2, 1] or a similar small example.

Step 6: Discuss Edge Cases (1 minute)

"This handles negative numbers, zero, and single-element arrays correctly..."

Strong Candidate Signals

Interviewers look for: (1) Clear explanation of XOR properties, (2) Recognition that this is optimal, (3) Clean, bug-free code, (4) Proactive discussion of edge cases, (5) Ability to discuss alternatives and trade-offs.

Summary

Key Takeaways

•The single-number problem is the canonical XOR application — memorize it and understand it deeply
•Algorithm: Initialize result to 0, XOR all elements, return result
•Complexity: O(n) time, O(1) space — optimal in both dimensions
•Works with negatives and zeros: XOR operates on bits, not values
•Edge cases: Single element, negatives, zeros, large numbers all handled correctly
•Real applications: Data integrity, checksums, database reconciliation
•Interview skills: Explain properties, code cleanly, trace examples, discuss alternatives

What's Next:

The single-number problem has a famous extension: what if two elements appear once while all others appear twice? This requires a clever twist on the XOR technique that we'll explore in the next page.

Page Complete

You've mastered the foundational XOR problem. The single-number technique is now part of your algorithmic toolkit. Next, we'll tackle the more challenging variant: finding two unique numbers.