Counting Set Bits Up to N

easy bit manipulation dp

Problem

For every integer i in the range [0, n], return its popcount (number of 1-bits) in O(n). Use the recurrence popcount(i) = popcount(i >> 1) + (i & 1).

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

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