Introduction

This problem looks similar to the classic XOR puzzle, but the parity pattern is reversed. If exactly one number appears an even number of times and every other distinct number appears an odd number of times, plain XOR does not directly reveal the answer, so the safest general approach is frequency counting.

Why XOR Alone Does Not Solve This Version

For the well-known problem where one value appears an odd number of times and all others appear an even number of times, XOR works because the even counts cancel out.

Here the situation is different:

• the target value appears an even number of times
• every other value appears an odd number of times

If you XOR the whole array, the even-repeating number disappears and the odd-repeating numbers remain mixed together.

For example, in:

[2, 2, 3, 3, 3, 5, 5, 5]

the answer is 2, but the XOR of the full array is:

2 ^ 2 ^ 3 ^ 3 ^ 3 ^ 5 ^ 5 ^ 5 = 3 ^ 5

That does not isolate the even-repeating number. So the first important insight is that this is not the standard XOR problem.

Use Frequency Counting

The straightforward and correct general solution is to count how many times each value appears, then return the one whose count is even.

1from collections import Counter
2
3def find_even_repeating(values: list[int]) -> int:
4    counts = Counter(values)
5
6    for value, count in counts.items():
7        if count % 2 == 0:
8            return value
9
10    raise ValueError("No even-repeating value found")
11
12print(find_even_repeating([2, 2, 3, 3, 3, 5, 5, 5]))

This runs in linear time and is easy to reason about. It also matches the real structure of the problem instead of forcing a bit trick where it does not fit.

Complexity and Data Structure Choices

Using a hash map or Counter gives:

• 'O(n) time'
• 'O(m) extra space, where m is the number of distinct values'

That is usually the right tradeoff for an unsorted array.

If the value range is known to be small and nonnegative, a counting array can also work:

1def find_even_repeating_small_range(values: list[int], max_value: int) -> int:
2    counts = [0] * (max_value + 1)
3
4    for value in values:
5        counts[value] += 1
6
7    for value, count in enumerate(counts):
8        if count > 0 and count % 2 == 0:
9            return value
10
11    raise ValueError("No even-repeating value found")

This is still the same idea as frequency counting. The only difference is the storage structure.

Be Careful About the Problem Assumptions

The problem is well-defined only if the input guarantees exactly one distinct value with even frequency. If the input can contain:

• more than one even-frequency value
• no even-frequency value
• negative numbers when you planned to use an index-based counting array

then the implementation needs extra validation or a more general data structure.

That is another reason the hash-map solution is a good default. It makes fewer assumptions about the input domain.

When a Smarter Trick Might Exist

Extra constraints can change the best answer. For example, if the array is sorted, you might exploit runs of equal values. If the value range is extremely small, a compact counting structure may be more efficient.

But for the general unsorted problem statement, frequency counting is the correct baseline. It is robust, linear-time, and conceptually honest about what information the input parity pattern actually gives you.

Common Pitfalls

• Applying the usual XOR trick without noticing that this problem has the opposite parity pattern.
• Assuming the input always contains exactly one even-frequency value without checking the real constraints.
• Choosing an array-based counting method when values can be negative or very large.
• Overcomplicating the problem when a simple frequency map already gives linear time.
• Confusing "appears an even number of times" with "is an even number."

Summary

• This is not the standard XOR parity problem.
• XOR cancels the even-repeating value instead of isolating it.
• The safest general solution is to count frequencies and return the value with an even count.
• A hash map gives linear time and works well for unsorted input.
• Only switch to more specialized tricks when the problem gives extra structure beyond the basic statement.