Single Number

EASY✓ CHIP-TIMEDLC #136 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A list where every value shows up twice except one lone outlier — find that one, in a single linear pass and no extra memory if you can manage it.

A list of integers arrives where every value shows up exactly twice, except for one lone value that appears only once — and the task is to identify that single outlier.

Nothing about the list's order or the position of the lone value is meaningful; the only fact that matters is which value fails to have a matching partner somewhere else in the list.

The result is that one integer, on its own — and the intended solution keeps to a single linear pass with no extra memory beyond a couple of variables.

arrays run up to tens of thousands of elements, always odd-length
every value except exactly one appears exactly twice
values can be negative, zero, or positive
the intended approach uses constant extra space

EX 01

nums = [2, 2, 1]

→ 1

smallest interesting case

EX 02

nums = [4, 1, 2, 1, 2]

→ 4

lone value up front

EX 03

nums = [1]

→ 1

minimum size, single element

The hintstake only what you need

HINT 1 THE NUDGE

Counting how many times each value appears works, but a map costs memory the problem doesn't strictly need — is there an operation that cancels duplicates for free?

HINT 2 THE STRUCTURE

XOR is its own inverse: a value XORed with itself vanishes to zero, and XOR with zero changes nothing. Order never matters either.

HINT 3 ONE STEP FROM THE ANSWER

Fold the whole array through XOR, one running accumulator. Every paired value cancels its partner out, and whatever survives is the lone one.

Coach's boardthe pattern, step by step

THE XOR FOLDPATTERN · XOR THE WHOLE ARRAYnums = [4, 1, 2, 1, 2]

RUNNING XOR

xor → 0

STEP 1

Fold every value through XOR — a value XORed with itself cancels to zero, so pairs vanish and only the loner remains.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/single-number.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for v in nums:
            result ^= v
        return result

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 6 LN

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = {}
        for v in nums:
            counts[v] = counts.get(v, 0) + 1
        for v, c in counts.items():
            if c == 1:
                return v
        return -1

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int v : nums) {
            result ^= v;
        }
        return result;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 9 LN

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int v : nums) {
            counts.merge(v, 1, Integer::sum);
        }
        for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return -1;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED