Dynamic Programming
Easy
Counting Bits
Given an integer n, return an array of the number of 1's for each number from 0 to n.
10 min read
Solve on LeetCodeProblem Understanding
We need to return an array ans of size n + 1 such that for each i, ans[i] is the number of 1's in the binary representation of i.
Example: n = 2
- 0 -> 0 (0)
- 1 -> 1 (1)
- 2 -> 10 (1)
- Output:
[0, 1, 1]
Algorithm Strategy
Instead of counting bits for each number individually (O(N log N)), we can use DP (O(N)).
Key Insight:
i(even):number_of_ones(i) == number_of_ones(i / 2)(shifting left adds a 0, count doesn't change).i(odd):number_of_ones(i) == number_of_ones(i / 2) + 1(last bit is 1).
Recurrence: dp[i] = dp[i >> 1] + (i & 1)
Interactive Visualization
Step 1 / 1
Initializing...
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.