Counting Bits

easy bit manipulation dp

Problem

Given an integer num, return an array of the number of 1's in the binary representation of every number in the range [0, num].

Inputn = 5

Output[0, 1, 1, 2, 1, 2]

popcount(0..5) computed bottom up.

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

function 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;
}

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;
    }
}

vector<int> countBits(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

Explanation

We need the number of set bits (the popcount) for every number from 0 to n. Counting each one from scratch would be wasteful, so we reuse answers we already computed using a tiny dynamic programming recurrence.

The key insight: dropping the last bit of i with i >> 1 gives a smaller number we have already solved. The only bit we lose is the lowest one, which is exactly i & 1. So dp[i] = dp[i >> 1] + (i & 1).

In words: the bit count of i equals the bit count of i with its last bit shaved off, plus one if that last bit was a 1.

Example for i = 5 (binary 101): 5 >> 1 = 2 (binary 10) which already has dp[2] = 1, and 5 & 1 = 1, so dp[5] = 1 + 1 = 2. Correct, since 101 has two ones.

Because every value is built from a smaller one in constant time, we fill the whole array in a single pass.

Time: O(n) Space: O(n)