Find the Badge Scanned Only Once, Without a Counting Map

Counting every badge in a map costs memory for every badge; XOR cancels each pair as it goes and leaves the one scanned once.

XOR finds the one value in a list that has no partner, in one pass and O(1) extra space, because equal values cancel. A building's door logs every badge scan: each visitor scans in and scans out, so every badge appears twice, except one visitor who left by the fire door and appears once. The log reads 9 4 12 9 7 4 12.

Which badge was scanned only once?

Every other badge appears twice.

The brute force counts. A map from badge to count, filled in one pass and then searched for a count of 1, is O(n) time and O(n) extra space for n scans; comparing every scan with every other is O(n²) time and O(1) space. The repeated cost of the map is memory spent on values that will cancel: a badge's count rises to 2 and is then ignored.

XOR removes the memory. It rests on three facts: x ^ x is 0, so a pair cancels; x ^ 0 is x, so 0 is a safe start; and the order of the operations does not matter, so the two scans of a badge cancel even with other badges between them. Folding every scan into one running XOR leaves exactly the badge without a partner.

A counting map against a running XOR

Counting mapO(n) time, O(n) space

Count every badge in a map, then find the one with a count of 1. The map holds an entry for every distinct badge.

Running XORO(n) time, O(1) space

XOR every scan into one integer. Each pair cancels as it completes, and the badge without a partner is what remains.

The trace follows the running XOR as eight bits, with each scan and the running value in the label.

The running XOR over the scans 9 4 12 9 7 4 12

Inputscans 9 4 12 9 7 4 12

Start = 0
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 0
Start at 0, which leaves any value it meets unchanged
Badge 9, running 9
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 0
8. 1
9 is 1001: the bits worth 8 and 1 turn on
Badge 4, running 13
1. 0
2. 0
3. 0
4. 0
5. 1
6. 1
7. 0
8. 1
4 turns on the bit worth 4
Badge 12, running 1
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 1
12 is 1100 and turns off the bits worth 8 and 4
Badge 9, running 8
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 0
8. 0
The second 9 cancels the first: 8 is the XOR of 4 and 12 alone
Badge 7, running 15
1. 0
2. 0
3. 0
4. 0
5. 1
6. 1
7. 1
8. 1
7 is 0111
Badge 4, running 11
1. 0
2. 0
3. 0
4. 0
5. 1
6. 0
7. 1
8. 1
The second 4 cancels the first: 11 is the XOR of 12 and 7
Badge 12, running 7
1. 0
2. 0
3. 0
4. 0
5. 0
6. 1
7. 1
8. 1
The second 12 cancels the first, and 7 is left

ResultThe running XOR ends at 7, the badge scanned once.

The listing runs both versions on the log.

badges.pypy

from collections import Counter


def scanned_once_with_counts(badges: list[int]) -> int:
    counts = Counter(badges)
    return next(badge for badge, count in counts.items() if count == 1)


def scanned_once_with_xor(badges: list[int]) -> int:
    running = 0
    for badge in badges:
        running ^= badge
    return running


badges = [9, 4, 12, 9, 7, 4, 12]
print("counting map:", scanned_once_with_counts(badges))
print("running XOR: ", scanned_once_with_xor(badges))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

counting map: 7
running XOR:  7

Both find 7. The XOR version reads each scan once and keeps one integer, so it is O(n) time and O(1) extra space. It answers only when exactly one value is unpaired and every other appears an even number of times; with two values unpaired it returns their XOR, and the counting map is the tool again.

Algorithms

← → move through sections and cards