Counting Bits | Problems

Given an integer n, return an array ans of length n+1 where ans[i] is the number of 1-bits in i.

Example: n = 5 → Output: [0,1,1,2,1,2]

Sample Input

—

Sample Output

—

Constraints

Test Cases

Case 1

Args: [2] Expected: [0,1,1]

Case 2

Args: [5] Expected: [0,1,1,2,1,2]

Topics

DP with Bit Trick

ans[i] = ans[i >> 1] + (i & 1).

function countBits(n) {
  const ans = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
  return ans;
}

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

Saved in this browser only. Private to you.