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.

Recognition Cues

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

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