Approach Summary
dp[i] = dp[i >> 1] + (i & 1). The number of 1-bits in i is same as i/2 plus the last bit.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Individual Popcount per Number | O(n log n) or O(n * 32) | O(1) auxiliary | Compute the set bits of each number from 0 to n independently using Brian Kernighan's algorithm. |
| 2 Approach 2: Dynamic Programming with Right Shift (Optimal) | O(n) | O(1) auxiliary | Reuse previous count via recurrence: dp[i] = dp[i >> 1] + (i & 1). |
Approach 1: Individual Popcount per Number
For each integer i from 0 to n, run a helper function that repeatedly clears the lowest set bit using x = x & (x - 1) until x == 0. While simple to reason about and requiring no state between numbers, it redundantly re-evaluates overlapping bit patterns for every integer.
Approach 1: Individual Popcount per Number Implementation
Approach 1: Individual Popcount per Number
class Solution {
private int popcount(int x) {
int cnt = 0;
while (x != 0) {
x &= (x - 1);
cnt++;
}
return cnt;
}
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 0; i <= n; i++) {
res[i] = popcount(i);
}
return res;
}
}class Solution {
public:
int popcount(int x) {
int cnt = 0;
while (x) {
x &= (x - 1);
cnt++;
}
return cnt;
}
vector<int> countBits(int n) {
vector<int> res(n + 1, 0);
for (int i = 0; i <= n; i++) {
res[i] = popcount(i);
}
return res;
}
};class Solution:
def countBits(self, n: int) -> list[int]:
def popcount(x: int) -> int:
cnt = 0
while x:
x &= (x - 1)
cnt += 1
return cnt
return [popcount(i) for i in range(n + 1)]function countBits(n) {
function popcount(x) {
let cnt = 0;
while (x !== 0) {
x &= (x - 1);
cnt++;
}
return cnt;
}
const result = [];
for (let i = 0; i <= n; i++) {
result.push(popcount(i));
}
return result;
}Approach 2: Dynamic Programming with Right Shift (Optimal)
Any number i in binary is simply the number i >> 1 with the bit (i & 1) appended to the right. Therefore, the total set bits of i is the set bits of i >> 1 plus 1 if the last bit was 1, or 0 if it was 0. Since i >> 1 < i, its solution is already available in the DP array. This allows computing each element in a single arithmetic operation.
Approach 2: Dynamic Programming with Right Shift (Optimal) Implementation
Approach 2: Dynamic Programming with Right Shift (Optimal)
class Solution {
public int[] countBits(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int digit = (i & 1);
dp[i] = dp[i >> 1] + digit;
}
return dp;
}
}class Solution {
public:
vector<int> countBits(int n) {
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
int digit = (i & 1);
dp[i] = digit + dp[i >> 1];
}
return 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 dpfunction countBits(n) {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}Edge Cases to Watch
- n = 0 (returns [0])
- n = 1 (returns [0, 1])
- Powers of two (e.g. 2, 4, 8, 16; each has exactly one 1-bit and resets pattern)
- Large values of n up to 10^5 (linear pass executes seamlessly under 5ms)
Master the Bit Manipulation Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Bit Manipulation pattern.
How to Recognize This Pattern
- Count set bits for all numbers 0..n
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)