Counting Bits

How it works

We want to find the number of set bits (1s) in every number from 0 to n.

A very important observation from binary representation is:

• Right-shifting a number by 1 (i >> 1) removes the least significant bit
• (i & 1) tells us whether the last bit of i is 1 or 0

So, the number of set bits in i can be built from a smaller number:

setBits(i) = setBits(i >> 1) + (i & 1)

This means each result depends only on a previously computed value, making it a perfect fit for Dynamic Programming.

Steps

1. Create a DP array dp of size n + 1
   • dp[i] stores the number of set bits in i
2. Initialize dp[0] = 0
3. For every number i from 1 to n:
   • Right shift i by 1 to get i >> 1
   • Check the last bit using (i & 1)
   • Compute:

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) space for the output array.

Things to watch for

Incorrect Bit Shift Operator

When using the DP recurrence dp[i] = dp[i >> 1] + (i & 1), a common mistake is using left shift instead of right shift, or confusing the operator precedence.

Off-by-One in Loop Bounds

The problem asks for bits count from 0 to n inclusive, meaning the result array should have n + 1 elements. A common mistake is creating an array of size n or iterating up to n - 1.

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for i in range(n + 1):
            dp[i] = dp[i >> 1] + (i & 1)
        return dp

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};