137. Single Number II

At a Glance

Topic: bit-manipulation
Pattern: Bit count modulo 3 (Bit Manipulation)
Difficulty: Medium
Companies: Amazon, Google, Facebook, Microsoft, Bloomberg
Frequency: Medium
LeetCode: 137

Problem (one-liner)

Every integer appears three times except exactly one value once. Find that 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

"Except one appears once" with triple duplicates
Const space forbids frequency map with large key domain — bitwise digit sums mod 3

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.

Loading diagram…

Approaches

Brute force — hash map counts mod 3 — O(n) time / O(n) space.
Optimal — track bits mod 3 with ones / twos masks — O(n) time / O(1) space.

Optimal Solution

Go

package main

func singleNumber(numbers []int) int {
	ones := 0
	twos := 0
	for _, value := range numbers {
		// bits that have appeared 1 mod 3 so far
		ones = (ones ^ value) &^ twos
		// bits that have appeared 2 mod 3 so far
		twos = (twos ^ value) &^ ones
	}
	return ones
}

JavaScript

function singleNumber(numbers) {
	let ones = 0;
	let twos = 0;
	for (const value of numbers) {
		ones = (ones ^ value) & ~twos;
		twos = (twos ^ value) & ~ones;
	}
	return ones;
}