Counting Bits Easy 0 attempts
LeetCode ↗

Counting Bits

Easy Dynamic ProgrammingMemoization LeetCode

Given an integer n, build an array of length n+1 where the value at each index i is the count of set bits (1-bits) in the binary representation of i.

Input Format
Implement countBits(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
n = 2
Output
[0,1,1]

Example 2

Input
n = 5
Output
[0,1,1,2,1,2]
Constraints
  • 0 <= n <= 10^5
Test Cases (2)
Case 1
Args: [2] Expected: [0,1,1]
Case 2
Args: [5] Expected: [0,1,1,2,1,2]
Topics
Dynamic ProgrammingMemoization

DP with Bit Trick

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

javascript
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.

JavaScript