LeetCode 136 – Single Number | Love Me Some Coding

Single Number is the problem that teaches XOR as a tool rather than a curiosity. The constraints — linear time, constant space — rule out the two obvious answers, and what is left is a one-line loop that looks like magic until you can name the three properties making it work.

The problem

Every element appears exactly twice except one, which appears once. Find it. The follow-up requires linear time and constant extra space.

[2,2,1]      -> 1
[4,1,2,1,2]  -> 4
[1]          -> 1
[-1,-1,-2]   -> -2      negatives work too

What the constraints rule out

Approach	Time	Space	Verdict
Hash set: add, remove on second sight	`O(n)`	`O(n)`	space fails
Sort, then scan for the odd one out	`O(n log n)`	`O(1)`	time fails
`2 · sum(set) - sum(nums)`	`O(n)`	`O(n)`	space fails, and overflows
XOR everything	`O(n)`	`O(1)`	✓

Give the hash set first — it is correct and it shows you understood the problem — and then say "the follow-up wants constant space, so I need something that cancels". Naming cancellation as the requirement is what leads to XOR rather than recalling it.

Three properties, and the result falls out

a ^ a = 0          a value cancels itself
a ^ 0 = a          zero is the identity
a ^ b = b ^ a      commutative, and associative

The third property is the one people skip, and it is what makes the algorithm work on unsorted input. Because order does not matter, the whole array can be rearranged mentally so the pairs sit together:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

Every duplicate annihilates its partner wherever it happens to be, and the loner is left standing. Walking through that regrouping out loud is the answer — the loop is a formality afterwards.

Java

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;              // XOR's identity, so it contributes nothing

        for (int num : nums) {
            result ^= num;           // pairs cancel wherever they are
        }

        return result;
    }
}

Seeding with 0 is not arbitrary — it is the identity element, the same role 0 plays for addition and 1 for multiplication. Starting with nums[0] and looping from index 1 also works and needs a guard for the empty array; seeding with the identity needs none.

No overflow is possible. XOR is bitwise, so unlike the sum-based tricks it cannot exceed the range of the type — worth mentioning, because the 2·sum(set) - sum(nums) approach is a genuine trap on large values.

Python

from functools import reduce
from operator import xor


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

reduce(xor, nums, 0) states the algorithm exactly: fold the array with XOR, starting from the identity. The explicit loop is equally good and clearer to most readers —

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

— and either is fine as long as you can say why it works. Reaching for reduce without the explanation reads as recall.

Complexity

	Time	Space
XOR fold	`O(n)`	`O(1)`

Every element must be read — the single number could be anywhere — so linear is optimal.

The family

XOR generalises further than it first appears, and these three are worth knowing as a set:

Problem	Twist	Idea
136	one single, rest twice	XOR everything
137	one single, rest three times	XOR no longer cancels — count bits mod 3
260	two singles, rest twice	XOR gives `a^b`; split by any set bit

Problem 260 is the elegant one: the total XOR is a ^ b, and any bit set in it is a bit where a and b differ. Partition the array by that bit and each half becomes problem 136. Problem 137 is the reminder that the trick is specific — XOR cancels pairs, and nothing about it cancels triples.

Missing Number (268) is the same idea with the indices XORed in alongside the values, so everything pairs off except the absent one.

What the interviewer is checking

That you notice the constraints eliminate the hash set and the sort.
The three XOR properties, and that you use all three — commutativity is what handles unsorted input.
That 0 is the identity, and why that makes it the right seed.
That XOR cannot overflow, unlike the sum tricks.
A single-element array, and negative values.
That you know the trick does not extend to triples, and what does.