338. Counting Bits

Return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i.

i & (i − 1) is i with its lowest 1 removed, so dp[i] = dp[i & (i − 1)] + 1.

1function countBits(n: number): number[] {
2  const dp = new Array(n + 1).fill(0);
3  for (let i = 1; i <= n; i++) {
4    dp[i] = dp[i & (i - 1)] + 1;
5  }
6  return dp;
7}

dp

dp[0] = 0.

1 / 0

Space: play/pause · ←/→: step