1. Understanding the Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

For example, when n = 5, the binary form of 3 is 11 (which has two 1-bits), so ans[3] = 2. The binary form of 4 is 100 (which has one 1-bit), so ans[4] = 1.

The Core Challenge:

Calculating set bits individually for each number takes extra work per integer. The real challenge is achieving an optimal solution that computes all results in a single pass in O(N) time without relying on built-in popcount functions.

2. The Naive Approach: Independent Popcount for Each Integer

The most intuitive, brute-force way to solve this problem is to iterate through every number from 0 to n and manually count its set bits using bitwise operations (like Kernighan's algorithm i & (i - 1)) or string conversions.

Trade-off Analysis

While this logic works fine for small inputs, it re-evaluates overlapping bit patterns repeatedly:

• Time Complexity: O(N log N) — For each of the N numbers, counting set bits takes O(log N) time (the number of bits in the integer).
• Space Complexity: O(1) — Excluding the output array of size O(N), no additional memory is allocated.

3. The Optimal Approach: Dynamic Programming via Right Shift (O(N) Time, O(1) Space)

To pass a senior-level technical interview, we want to compute the answer for each integer in O(1) time per element, yielding a total time complexity of O(N).

We can achieve this by recognizing a fundamental relationship between an integer i and its right-shifted version i >> 1 (which is equivalent to i // 2):

• Right-shifting a binary number by one bit removes its least significant bit (LSB).
• Therefore, the number of set bits in i is equal to the number of set bits in i >> 1 (a state we have already computed and stored), plus 1 if the LSB of i was set (i.e., if i is odd).

Mathematically, the transition state is simply: ans[i] = ans[i >> 1] + (i & 1).

This single observation completely unifies the logic, allowing us to compute every entry in O(1) constant time building upon previous calculations!

4. The Logic Step-by-Step

1. Initialize an integer array ans of size n + 1 filled with 0s.
2. Base Case: ans[0] = 0 (since 0 has zero set bits in binary).
3. Iterate Through Numbers: Loop from i = 1 up to n:
   • Look up the previously calculated set-bit count for i >> 1 (which is ans[i >> 1]).
   • Add (i & 1) to check if the current number i ends with a 1 bit (odd number).
   • Store the result at ans[i].
4. Return the populated ans array.

5. Complexity Analysis

• Time Complexity: O(N) — We compute the set-bit count for each number from 0 to n exactly once using a simple O(1) arithmetic lookup.
• Space Complexity: O(1) — No auxiliary data structures are used beyond the required ans output array.

6. Code Implementations

Expand the sections below to see the optimal O(N) time dynamic programming implementations across different languages.

class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        
        for i in range(1, n + 1):
            # ans[i] = set bits of (i // 2) + (1 if i is odd else 0)
            ans[i] = ans[i >> 1] + (i & 1)
            
        return ans

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            // ans[i] = set bits of (i / 2) + (1 if i is odd else 0)
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        return ans;
    }
}

#include <vector>

class Solution {
public:
    std::vector<int> countBits(int n) {
        std::vector<int> ans(n + 1, 0);
        
        for (int i = 1; i <= n; ++i) {
            // ans[i] = set bits of (i / 2) + (1 if i is odd else 0)
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        return ans;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the "Counting Bits" dynamic programming pattern! The key takeaway from this problem is discovering the bitwise transition rule: a number's set-bit count depends directly on a smaller subproblem (i >> 1) plus its own least significant bit (i & 1). By leveraging this recurrence relation, you turned an O(N log N) repeated bit counting problem into an elegant O(N) linear-time dynamic programming solution. Keep this state-reuse technique in your mental toolkit, as it is a crucial bridge between low-level bit manipulation and top-tier DP interview problems!