beginner7 min read·Updated October 8, 2026

Single Number (XOR) Explained: Tracing [4, 1, 2, 1, 2]

Master the XOR pattern for finding the lone element in [4, 1, 2, 1, 2]. Build a mental model of bitwise cancellation and practice edge cases.

By Learnisim AI·Published October 8, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic understanding of arrays
  • Introduction to binary numbers and bitwise operations
Finding the Single Number via Bitwise XOR: nums = [4, 1, 2, 1, 2] 1. The Duplicate Maze & Naive Cost 4 Lone 1 pair 2 pair 1 pair 2 pair Why Hash Maps Break for Large Datasets • Hash Map: O(n) Time, O(n) Auxiliary Memory • Memory bottleneck when scaling to millions of items Goal: O(n) Time & Strictly O(1) Constant Space The XOR Model (^): Cancellation as a Switchboard • Identical bits cancel to 0: (x ^ x = 0) • Zero identity preserves value: (0 ^ x = x) Commutative & Associative Tracing Accumulator: acc = acc ^ num (Commutative grouping: [1^1] ^ [2^2] ^ 4) Start acc = 0 ^ 4 acc = 4 ^ 1 acc = 5 ^ 2 acc = 7 ^ 1 (pair) acc = 6 ^ 2 (pair) Result = 4 Notice: All paired duplicates cancel out to 0 regardless of order. Only the lonely 4 remains! O(n) Time | O(1) Space
Single number in [4, 1, 2, 1, 2] overview diagram
Why

Why Standard Arrays Break When Hunting for the Lone Item

Phase 1: The Duplicate Maze

Imagine you are handed a list of integers: [4, 1, 2, 1, 2]. Almost every number in this array appears exactly twice, but one single number hides in the crowd without a partner. Your job is to spot that lonely value. If you scan nums = [4, 1, 2, 1, 2], your human eye quickly isolates 4 because 1 and 2 immediately cancel out in your memory.
Writing code to do this on a massive dataset forces a choice. The most intuitive reflex is to grab a hash map or a frequency counter. You iterate through the array, tally up occurrences, and then loop through your counts to find the key with a frequency of 1.
python
# The frequency map approach
counts = {}
for x in [4, 1, 2, 1, 2]:
    counts[x] = counts.get(x, 0) + 1
for k, v in counts.items():
    if v == 1:
        print(k) # prints 4
While this correctly identifies 4, it demands extra memory proportional to the size of the array to store those counts. When datasets scale to millions of elements, allocating auxiliary memory becomes a bottleneck. The challenge deepens when constraints demand time and strictly constant extra space.
python
def find_lone_element(nums):
    # How would you track frequencies without a dictionary?
    pass
Why Standard Arrays Break When Hunting for the Lone Item Dataset: [4, 1, 2, 1, 2] — Every value appears twice except one single lonely number nums = 4 Lone! 1 2 1 2 cancels cancels Goal: Find lone item in O(1) space Phase 1: Frequency Counter (Hash Map) 1. Iterate & tally occurrences in hash map Hash Table Store { 4:1, 1:2, 2:2 } Auxiliary Memory O(N) Second Scan Loop keys for frequency == 1 The Memory Bottleneck Allocates extra memory proportional to array size. Fails strict constant space constraints on massive datasets. Phase 2: Side-Channel Bitwise (XOR) 1. Accumulate XOR sum across all elements Bitwise Cancellation Property A ^ A = 0 | A ^ 0 = A 4 ^ 1 ^ 2 ^ 1 ^ 2 ===> 4 ^ (1^1) ^ (2^2) = 4 Zero Auxiliary Memory Replaces counting tables with pure algebraic cancellation. O(N) Time and strict O(1) Constant Space achieved.
Why Standard Arrays Break When Hunting for the Lone Item diagram
Model

The XOR Model: Cancellation as a Switchboard

Phase 2: The XOR Model

To hunt the single lone item in our dataset nums = [4, 1, 2, 1, 2], we need an operator that acts like an invisible pair-canceler. That operator is the bitwise XOR (exclusive OR), denoted in programming as ^. When you XOR two identical numbers together, they completely wipe each other out to zero because every matching bit pair neutralizes. For instance, 2 ^ 2 evaluates to 0 in binary because 10 ^ 10 has matching bits in every position.
Think of the accumulator as a single memory slot that starts at 0. As we feed each number from our working example into this slot via XOR, duplicate numbers enter twice and thus collide and cancel themselves out. The repeating 1s in [4, 1, 2, 1, 2] will cancel each other, and the repeating 2s will do the same. Only the number that appears an odd number of times—our target 4—remains standing at the end, because nothing was paired with it to neutralize its bits.
This behavior relies on two algebraic properties of XOR: commutativity (order doesn't matter, so 1 ^ 2 ^ 1 is the same as 1 ^ 1 ^ 2) and associativity (grouping doesn't matter). Because of these properties, every pair of duplicates collapses to zero regardless of where they sit in the array, leaving only the unmatched element to define the final accumulator value.
Try this: Explain in your own words why applying XOR across [2, 2, 1] leaves behind 1, referencing the cancellation property of identical bits.
The XOR Model: Cancellation as a Switchboard Dataset: nums = [4, 1, 2, 1, 2] → Duplicates cancel out via bitwise XOR (^) 1. Input Stream (nums) 4 (unpaired) 1 (first) 2 (first) 1 (duplicate) 2 (duplicate) 2. The Accumulator Core (Starts at 0, applies ^ operator sequentially) Start 0 acc = 0 ^ 4 4 0 ^ 4 = 4 ^ 1 then ^ 1 4 1^1=0, keeps 4 ^ 2 then ^ 2 4 2^2=0, keeps 4 Result 4 Lone Survivor Identity & Self-Cancellation • n ^ n = 0 (Identical bits neutralize) • n ^ 0 = n (Zero acts as identity) Commutative & Associative • Order & grouping do not matter • (1^2^1^2) = (1^1) ^ (2^2) = 0 Why O(N) Time & O(1) Space? • Single pass through array (O(N)) • Only 1 accumulator variable (O(1))
The XOR Model: Cancellation as a Switchboard diagram
Worked example

Tracing the Bitwise XOR Operator Step by Step on [4, 1, 2, 1, 2]

Phase 3: Walking the Accumulator

Now we put the XOR model to work on our locked dataset: . Recall that our goal is to find the single number that appears only once, while all other numbers appear twice, achieving time and space without a hash set.

Given

- Input array:
- Initial accumulator:

Steps

1. Iteration 1: Process 4. Compute . In binary, (4).
2. Iteration 2: Process 1. Compute . Compute (5).
3. Iteration 3: Process 2. Compute . Compute (7).
4. Iteration 4: Process 1 (the duplicate). Compute . Compute (6). Notice how the first 1 and the second 1 cancel each other out through bit flipping.
5. Iteration 5: Process 2 (the duplicate). Compute . Compute (4). The duplicate 2 neutralizes the earlier 2.

Result

- Final accumulator value: .
•The matching expected result is confirmed, and the algorithm terminates having used zero extra memory.
Try this: Given a secondary array nums = [2, 2, 1], trace the accumulator value after each element is processed with XOR.
Phase 3: Walking the Accumulator on [4, 1, 2, 1, 2] Sequential XOR steps: duplicates cancel out, leaving the single lone number ACCUMULATOR acc = 0 INPUT STREAM (processed left to right): 4 , 1 , 2 , 1 , 2 1. Process 4 0 ^ 4 = 4 acc = 4 (0100) 2. Process 1 4 ^ 1 = 5 acc = 5 (0101) 3. Process 2 5 ^ 2 = 7 acc = 7 (0111) 4. Process 1 (Duplicate) 7 ^ 1 = 6 First '1' cancels out! 5. Process 2 (Duplicate) 6 ^ 2 = 4 Second '2' neutralizes earlier '2' ALGORITHM TERMINATES Final Accumulator = 4 Lone number found with zero extra memory! Key Takeaway: Commutative & Associative Pairs cancel out to 0 regardless of order. Try tracing nums = [2, 2, 1] on your scratchpad to confirm!
Tracing the Bitwise XOR Operator Step by Step on [4, 1, 2, 1, 2] diagram
Apply

Transferring the XOR Pattern to Missing Elements and Beyond

Phase 4: Beyond the Single Duplicate Pair

Now that you have seen how acc ^= x systematically vaporizes pairs and leaves the lone value 4 stranded in nums = [4, 1, 2, 1, 2], it is time to deploy this exact bitwise cancellation mechanism to a neighboring puzzle. What happens if the array contains a missing number from a sequence rather than a duplicate pair?
Suppose you are given an array containing distinct numbers taken from , but one number is missing. If you take the XOR sum of all numbers in the array and also XOR that result with all expected numbers from 0 up to , every number that appears twice will cancel itself out. The missing number, appearing only once in the sequence stream, will remain.
Consider a mini variant with seq = [3, 0, 1] where . The expected universe is . If you accumulate 3 ^ 0 ^ 1 from the array and 0 ^ 1 ^ 2 ^ 3 from the complete sequence, identical values collide and vanish, leaving just the missing value behind in time and auxiliary memory.
python
def find_missing_number(nums):
    acc = 0
    n = len(nums)
    for i, x in enumerate(nums):
        acc ^= x ^ (i + 1)
    return acc
By framing problems as parity streams where cancellation is guaranteed, you stop fighting memory overhead and let the properties of binary arithmetic do the heavy lifting.
python
def solve_missing(nums):
    # Apply the XOR cancellation pattern to find the missing element
    pass

FAQ

How does XOR find the single number in [4, 1, 2, 1, 2]?
XORing all numbers together causes identical pairs to cancel each other out due to the property x ^ x = 0. Because 1 ^ 1 and 2 ^ 2 cancel to zero, only the unpaired number 4 remains.
What is the time and space complexity of using XOR for the Single Number problem?
The time complexity is O(N) because we iterate through the array once. The space complexity is O(1) since we only use a single accumulator variable, avoiding extra memory like hash sets.
Does the order of numbers in the array affect the XOR result?
No. XOR is both commutative and associative, meaning the order in which you XOR the numbers does not change the final outcome.
What happens if every number appears three times instead of twice?
The standard XOR trick only works for pairs (even counts). If every element appears three times except one, you need to track the bit counts modulo 3 instead of using simple XOR.

Keep learning