Single Number

EASY✓ CHIP-TIMEDLC #136 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

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

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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED