Introduction

When every value in an array appears exactly twice except one, the cleanest solution is not sorting or counting with a map. It is a bitwise XOR pass, which finds the unpaired element in linear time and constant extra space.

Why XOR Solves the Problem

XOR has two properties that make this work:

• 'a ^ a equals 0'
• 'a ^ 0 equals a'

Because XOR is also associative and commutative, pairs cancel no matter where they appear in the array. After processing every element, only the unique value remains.

For the array 4, 3, 2, 4, 1, 3, 2, the cancellation looks like this conceptually:

• '4 ^ 4 becomes 0'
• '3 ^ 3 becomes 0'
• '2 ^ 2 becomes 0'
• '0 ^ 0 ^ 0 ^ 1 leaves 1'

That gives you the answer in one pass.

The Best General Solution for This Exact Problem

Here is a small Python implementation:

1def find_unpaired(values):
2    result = 0
3    for value in values:
4        result ^= value
5    return result
6
7numbers = [4, 3, 2, 4, 1, 3, 2]
8print(find_unpaired(numbers))

This runs in O(n) time and O(1) extra space.

That is hard to beat because every element must be inspected at least once, so O(n) is already optimal in time. The XOR solution also avoids allocating a dictionary or sorting the array.

When a Hash Map Is Still Useful

The XOR trick only works under very specific assumptions:

• every paired value appears exactly twice
• exactly one value appears once
• values are integers or at least types where XOR makes sense

If the rules are more general, a counting structure is safer.

1from collections import Counter
2
3def find_single_by_count(values):
4    counts = Counter(values)
5    for value, count in counts.items():
6        if count == 1:
7            return value
8    raise ValueError("no unpaired value found")
9
10print(find_single_by_count([10, 10, 7, 5, 5]))

This still runs in linear time, but it uses extra memory proportional to the number of distinct values.

Sorting Is Usually Not the Best First Choice

Another valid approach is to sort the array and scan it in pairs. That works well enough for interviews or when the array is already sorted, but the runtime becomes O(n log n) because of the sort.

1def find_unpaired_sorted(values):
2    values = sorted(values)
3    i = 0
4    while i < len(values) - 1:
5        if values[i] != values[i + 1]:
6            return values[i]
7        i += 2
8    return values[-1]
9
10print(find_unpaired_sorted([4, 3, 2, 4, 1, 3, 2]))

That is fine if you also need the sorted order for some other reason. If the only goal is the unpaired element, XOR is more direct.

How to Explain the XOR Method Clearly

People often know the code but struggle to explain why it works. The clean explanation is:

1. every paired value cancels itself under XOR
2. order does not matter
3. zero disappears under XOR with the remaining value

That makes the proof small and complete.

Edge Cases to Think About

The XOR method handles negative integers as well because it operates on bit patterns, not on numeric sign semantics in a special way. It also works regardless of where the unpaired element appears.

What it does not do is validate the input contract. If the array contains two different unpaired values, the result becomes the XOR of those values, not a meaningful answer to the original problem.

So in production code, decide whether the input guarantee is trusted. If not, add validation or use a counting approach.

Common Pitfalls

The biggest pitfall is applying XOR to a problem that does not meet the “all others appear exactly twice” rule. In that case, the result is not reliable.

Another mistake is choosing a hash map first out of habit. A counting solution works, but it is more memory-heavy than needed for this exact problem.

A third issue is forgetting that sorting changes the time complexity. It may simplify reasoning, but it is not the most efficient route here.

Summary

• XOR is the best fit when every element appears twice except one.
• The method runs in O(n) time and O(1) extra space.
• It works because equal values cancel under XOR.
• Use a hash map when the occurrence pattern is more general.
• Use sorting only when sorted order is also useful for the broader task.