268. Missing Number

At a Glance

• Topic: bit-manipulation
• Pattern: XOR / Gauss sum (Bit Manipulation)
• Difficulty: Easy
• Companies: Amazon, Microsoft, Google, Bloomberg, Facebook
• Frequency: Very High
• LeetCode: 268

Problem (one-liner)

numbers contains len(numbers) distinct values drawn from 0..len(numbers) inclusive with exactly one missing. Return the missing value in O(n) time, prefer 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

• Range [0..n] with length n array — one hole
• XOR all indices and values, or use arithmetic sum identity

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 — sort and scan — O(n log n).
• Hash set — O(n) time / O(n) space.
• Optimal — XOR pairing or sum formula — O(n) time / O(1) space.

Optimal Solution

Go

package main

func missingNumber(numbers []int) int {
	xorAll := len(numbers)
	for index := range numbers {
		xorAll ^= index ^ numbers[index]
	}
	return xorAll
}

JavaScript

function missingNumber(numbers) {
	let xorAll = numbers.length;
	for (let index = 0; index < numbers.length; index++) {
		xorAll ^= index ^ numbers[index];
	}
	return xorAll;
}

Walkthrough

numbers = [3, 0, 1] (missing 2), length 3.

Accumulate xorAll starting with n, then for each index index, fold index and numbers[index]. Every present value cancels with its index partner except the missing number pairs only with its index, leaving the missing.

Invariant: XOR of multiset {0..n} xor multiset of array leaves missing.

Edge Cases

• Missing 0
• Missing n
• Single element [0] missing 1 or inverse per length

Pitfalls

• Integer overflow on sum approach — XOR avoids it
• XOR vs sum when duplicates exist — wrong problem variant

Similar Problems

• 136. Single Number — XOR cancellation theme.
• 338. Counting Bits — uses the full 0..n index space differently.

Variants

• Find two missing (bitmask / sum equations).
• Cyclic sort template on [1..n] (different pattern).

Mind-Map Tags

#xor #missing-value #index-match #range-0-n #linear