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.

Recognition Cues

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

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 — 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;
}

Walkthrough

Each bit position across numbers sums counts; contributions from triples cancel mod 3; singleton leaves residue in ones.

Invariant: ones holds XOR-like residue for bits seen 1 mod 3; twos for 2 mod 3; clears align when third copy arrives.

Edge Cases

• All bits singleton across negatives — two's complement behaves per-bit
• Minimum length 4 per constraints

Pitfalls

• Naive XOR — fails when duplicates are three not two
• Confusing &^ vs & ~ between languages

Similar Problems

• 136. Single Number — pairs cancel with XOR.
• 268. Missing Number — XOR structure over index/value pairs.

Variants

• General k-appearances except one — count bits mod k with more state registers.
• Single Number IV (appear four times) — analog state machine.

Mind-Map Tags

#mod-3 #bits #finite-state #xor-generalization #single-number