LeetCode · #338
Counting Bits Solution
Return an array where ans[i] is the number of 1 bits in the binary representation of i, for 0 ≤ i ≤ n.
01
Section One · Problem
Problem Statement
Example
Input: n = 5 Output: [0,1,1,2,1,2]
// 0→0, 1→1, 10→1, 11→2, 100→1, 101→2
02
Section Two · Approach 1
Count Each — O(n log n)
For each number 0..n, count its bits using Brian Kernighan's trick. O(log n) per number.
Better: Use DP:
dp[i] = dp[i >> 1] + (i & 1). The bit count of i is the bit count of i/2 plus whether the last bit is set. O(1) per number, O(n) total.03
Section Three · Approach 2
DP — O(n) time, O(1) extra
dp[i] = dp[i >> 1] + (i & 1). Right-shifting i removes the last bit — we already know the bit count of the shifted value. Add 1 if the removed bit was 1.
💡 Mental model: "How many 1s in 13 (1101)?" = "How many 1s in 6 (110)?" + "Is the last bit 1?". 6 has 2 ones, last bit is 1 → 3.
Alternative DP:
dp[i] = dp[i & (i-1)] + 1. Uses Brian Kernighan's trick: i & (i-1) removes the lowest set bit. The bit count increases by exactly 1.04
Section Four · Trace
Visual Walkthrough
Counting Bits — DP
05
Section Five · Implementation
Code — Java & Python
Java — DP
class Solution {
public int[] countBits(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++)
dp[i] = dp[i >> 1] + (i & 1);
return dp;
}
}
Python — DP
class Solution:
def countBits(self, n: int) -> list[int]:
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Count each | O(n log n) | O(n) |
| DP ← optimal | O(n) | O(n) output |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| n=0 | 0 | Return [0]. |
| n=1 | 1 | Return [0,1]. |
| Power of 2 | n=8 | dp[8]=dp[4]+0=1. Single bit. |
⚠ Common Mistake: Off-by-one: array should be size
n+1 (indices 0 to n inclusive).