Introduction

This array problem looks similar to the classic "every element appears twice except one" interview question, but the odd-frequency condition changes the solution completely. When every repeated value appears 3, 5, or another odd number of times, you need to be careful because the usual XOR shortcut no longer isolates the single element.

Why XOR Fails in This Variant

XOR works when repeated values appear an even number of times, because pairs cancel out. Here, repeated values appear an odd number of times greater than 1, so each repeated value contributes one surviving copy to the XOR result.

Consider this array:

[4, 4, 4, 9, 9, 9, 12]

If you XOR every element, you get:

4 ^ 4 ^ 4 ^ 9 ^ 9 ^ 9 ^ 12
= 4 ^ 9 ^ 12

That is not equal to 12. It is just the XOR of all distinct values with odd frequency. So a plain parity-based trick is not enough.

This is the core lesson: the moment the repeated values are not all the same frequency, counting becomes the reliable tool.

Count Frequencies in Linear Time

The straightforward solution is to scan the array once, count occurrences, and then return the value with count 1. This is O(n) time and O(n) extra space.

1def find_single_value(values):
2    counts = {}
3
4    for value in values:
5        counts[value] = counts.get(value, 0) + 1
6
7    for value, count in counts.items():
8        if count == 1:
9            return value
10
11    raise ValueError("No value appears exactly once")
12
13
14data = [7, 5, 7, 7, 5, 5, 11, 3, 3, 3, 11, 11, 11]
15print(find_single_value(data))  # 11 is not unique here

The sample above is intentionally wrong for the stated rule because 11 appears four times in total. That is the kind of input validation you should think about while testing. A valid example is:

data = [7, 7, 7, 5, 5, 5, 3, 3, 3, 11]
print(find_single_value(data))  # 11

If you want stricter validation, check that every non-unique value appears an odd number of times greater than 1.

1def find_single_value_strict(values):
2    counts = {}
3
4    for value in values:
5        counts[value] = counts.get(value, 0) + 1
6
7    unique = [value for value, count in counts.items() if count == 1]
8    if len(unique) != 1:
9        raise ValueError("Expected exactly one unique value")
10
11    for value, count in counts.items():
12        if value != unique[0] and (count <= 1 or count % 2 == 0):
13            raise ValueError("Repeated values must have odd counts greater than 1")
14
15    return unique[0]

If You Can Reorder the Array

If extra memory is a concern and sorting is allowed, sort the array and scan runs of equal values. The unique element will be the only run with length 1.

1def find_single_by_sorting(values):
2    values.sort()
3    i = 0
4
5    while i < len(values):
6        j = i + 1
7        while j < len(values) and values[j] == values[i]:
8            j += 1
9
10        if j - i == 1:
11            return values[i]
12
13        i = j
14
15    raise ValueError("No value appears exactly once")
16
17
18data = [21, 8, 21, 8, 8, 21, 13]
19print(find_single_by_sorting(data))  # 13

This version runs in O(n log n) time. It uses less extra memory if the sort is in place, but it mutates the input. That tradeoff is often acceptable in batch processing and less acceptable in library code.

Choosing the Right Approach

Use frequency counting when:

• you want the clearest code
• input order must be preserved
• 'O(n) expected time matters more than memory'

Use sorting when:

• you can modify the array
• memory pressure matters more than raw speed
• the data may already be partially sorted

There is no general constant-space trick comparable to the even-frequency XOR pattern for this exact problem. If someone claims there is, inspect the assumptions carefully.

Common Pitfalls

• Applying XOR out of habit. It solves a different problem and silently produces the wrong answer here.
• Skipping validation. If two values appear once, or a repeated value appears an even number of times, the problem constraints are broken.
• Forgetting that sorting changes the input. That can surprise callers that reuse the same list later.
• Assuming "odd repeats" means "three repeats". The algorithm must work for 3, 5, 7, and any other odd count above 1.

Summary

• This variant cannot be solved by plain XOR because odd-frequency duplicates do not cancel out.
• A hash map gives a direct O(n) time solution with O(n) extra space.
• Sorting and scanning runs is a valid alternative when input mutation is acceptable.
• Input validation matters because small constraint violations change the problem.
• The safest general strategy is to count occurrences explicitly.