Single Number — InterviewPrepKit

Solving tips

XOR fold is the canonical tool: XOR every element together, paired values cancel (x^x=0) and the loner survives (x^0=x).
Seed the accumulator with 0 (XOR's identity); one pass, one variable, O(n) time and O(1) space, satisfying the constant-space requirement a hash set would violate.
XOR is commutative and associative, so scattered duplicates cancel regardless of order.
Caveat: this only works when the odd one appears once and all others an even number of times; 'appears three times' (Single Number II) needs mod-3 bit counting instead.

Problem

You are given a non-empty array nums in which every element appears exactly twice except for one element, which appears exactly once. Return that single element. You must do it in linear time using only constant extra space.

Examples

[2, 2, 1] → 1 — the two 2s pair up; 1 is alone.
[4, 1, 2, 1, 2] → 4 — the 1s and 2s each pair up; 4 is alone.
[7] → 7 — a single element with no partner.

Constraints

1 <= len(nums) <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Every element appears twice except one, which appears once.

Required: O(n) time and O(1) extra space.

Think about it first

Hint 1

A hash map of counts, or a set you toggle membership in, finds the loner — but both use O(n) extra space, which the problem forbids.

Hint 2

XOR has two magic properties: `x ^ x = 0` (a value cancels itself) and `x ^ 0 = x` (zero is the identity). And XOR doesn't care about order.

Hint 3

XOR every element of the array together. Each paired value cancels to `0`, and the lone value XORed with `0` is itself — so the running XOR *is* the answer, in one pass with a single variable.

TL;DR

XOR the whole array; paired values cancel and the loner remains — O(n) time, O(1) space.

Approach 1 — Brute force: hash set (or counter)

The naive intuition: track what you’ve seen. Toggle each value in a set — add on first sight, remove on second — so only the unpaired value is left.

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop()

Complexity: O(n) time, O(n) space for the set.

Why we can do better: it meets the time bound but blows the O(1) space requirement — in the worst case the set holds ~n/2 elements. XOR removes the space entirely.

Approach 2 — XOR fold

The insight: XOR is self-inverse — x ^ x = 0 — and it is commutative and associative, so the order you combine values in doesn’t matter. Fold every element together with XOR: each value that appears twice meets its twin somewhere in the fold and the pair collapses to 0, no matter how the duplicates are scattered. The one value without a partner is XORed only with the accumulated 0, and x ^ 0 = x, so it survives as the final result. One variable, one pass, no extra space.

At the bit level, XOR compares the two operands column by column and outputs 1 only where the bits differ. Two copies of the same number agree in every column, so they XOR to all-zeros; that is why pairs vanish.

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

Walkthrough on [4, 1, 2, 1, 2] (result starts at 0):

num	result before	result after (`^= num`)
4	0	4
1	4	5
2	5	7
1	7	6
2	6	4

Returns 4. ✓ Reordering the array as [1, 1, 2, 2, 4] makes it obvious: (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4.

Complexity: O(n) time, O(1) space — one accumulator.

A one-liner using the same fold:

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        return reduce(xor, nums, 0)

Common pitfalls

Seeding with the wrong identity: start the accumulator at 0 (XOR’s identity). Seeding with nums[0] also works only if you then skip that element — easy to double-count.
Reaching for sum tricks: 2 * sum(set(nums)) - sum(nums) gives the same answer but uses O(n) space for the set — no better than the hash approach.
Assuming “twice” means adjacent: duplicates can be anywhere; XOR’s order-independence is exactly what makes that irrelevant.
Generalizing carelessly: this XOR fold only works when the odd one out appears once and everyone else an even number of times. “Every other element appears three times” (Single Number II) needs a different bit-counting scheme.

Pattern takeaway

XOR is the canonical tool for “find the unpaired element”: folding a collection with XOR cancels every value that appears an even number of times and leaves the odd one out. Remember the two identities — x ^ x = 0 and x ^ 0 = x — and that order never matters, and a whole class of “find the single/different value” problems collapses to one pass and one variable.