136. Single Number

At a Glance

• Topic: bit-manipulation
• Pattern: XOR cancelation (Bit Manipulation)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Apple
• Frequency: Very High
• LeetCode: 136

Problem (one-liner)

Every element appears twice except one value that appears once. Return that unique value in O(n) time and O(1) extra space.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Exactly one element appears once" — others appear twice
• Linear-time const-space restriction screams XOR

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — count with hash map — O(n) time / O(n) space.
• Optimal — XOR across the array — O(n) time / O(1) space — duplicates cancel.

Optimal Solution

Go

package main

func singleNumber(numbers []int) int {
	result := 0
	for _, value := range numbers {
		result ^= value
	}
	return result
}

JavaScript

function singleNumber(numbers) {
	let result = 0;
	for (const value of numbers) {
		result ^= value;
	}
	return result;
}

Walkthrough

Input: [4, 1, 2, 1, 2]

Invariant: XOR of multiset where each duplicate appears twice leaves singleton.

Edge Cases

• Single element array
• Negative numbers (two's complement XOR still valid)

Pitfalls

• Using XOR when duplicates appear three times (wrong problem — see Single Number II)

Similar Problems

• 268. Missing Number — XOR/sum on [0..n] complement set.
• 137. Single Number II — triples version.

Variants

• Two distinct singles if other numbers appear twice — XOR + partition (different problem).
• Find single in sorted array — BS variant.

Mind-Map Tags

#xor #cancel-pairs #bit-manipulation #linear-scan