Skip to content
RED SAGSkills
easy15 ptsbit-manipulationdynamic-programming

Set-Bit Count Table

Given a non-negative integer n, return an array table of length n + 1 where table[i] is the number of 1 bits in the binary form of i.

Aim for a single pass that reuses answers you have already computed instead of counting bits from scratch for every number.

Example 1

Input: n = 2
Output: [0,1,1]
Explanation: 0 is 0, 1 is 1, 2 is 10.

Example 2

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

Constraints

  • 0 <= n <= 10^5
Hint 1

i >> 1 drops the last bit of i, and you already know its count.

Hint 2

Add i & 1 to account for the dropped bit.

Good practice for: Embedded Systems Engineer, Backend Developer, Game Developer, Blockchain Developer, Machine Learning Engineer

Run checks your code on 3 sample tests. Submit runs all 6 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.