338. Counting Bits

At a Glance

• Topic: bit-manipulation
• Pattern: DP + bit relation (Bit Manipulation)
• Difficulty: Easy
• Companies: Amazon, Google, Facebook, Apple, Microsoft
• Frequency: High
• LeetCode: 338

Problem (one-liner)

For every index in [0, limit], return an array where entry index is the number of 1 bits in binary index.

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

• "Counting bits" for all numbers up to n
• Recurrence: count[index] = count[index >> 1] + (index & 1)

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 — popcount each independently — O(n log n) time.
• Optimal — DP leveraging highest power of two or shift recurrence — O(n) time / O(n) output space.

Optimal Solution

Go

package main

func countBits(limit int) []int {
	result := make([]int, limit+1)
	for value := 1; value <= limit; value++ {
		// same popcount as half, plus lowest bit contribution
		result[value] = result[value>>1] + value&1
	}
	return result
}

JavaScript

function countBits(limit) {
	const result = new Array(limit + 1).fill(0);
	for (let value = 1; value <= limit; value++) {
		result[value] = result[value >> 1] + (value & 1);
	}
	return result;
}

Walkthrough

limit = 5 → build table:

Invariant: result[value] matches popcount by inductive structure on binary tree of prefixes.

Edge Cases

• limit = 0 → [0]
• Max limit within problem bound

Pitfalls

• Off-by-one on array size limit+1
• Using float / log without integer recurrence

Similar Problems

• 191. Number of 1 Bits — single-value popcount.
• 268. Missing Number — xor index-value relationship.

Variants

• Use result[value] = result[value & (value-1)] + 1 (clear lowest bit step).
• Parallel popcount with SIMD (not interview).

Mind-Map Tags

#dp #popcount #bit-relation #prefix-table #on