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.

Recognition Cues

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

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