Math & Bits · 047Easy
Counting Bits
Given an integer n, return an array of length n + 1 where ans[i] is the number of 1-bits in the binary representation of i.
Constraints
- 0 <= n <= 10^5
Examples
countBits(2) -> [0, 1, 1] countBits(5) -> [0, 1, 1, 2, 1, 2] countBits(0) -> [0] countBits(1) -> [0, 1] countBits(3) -> [0, 1, 1, 2] countBits(8) -> [0, 1, 1, 2, 1, 2, 2, 3, 1] // powers of two drop back to 1
Edge cases
- n = 0 returns [0].
- The result has n + 1 entries, not n.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — count the bits of each number independently.
- Target
- O(n) time — DP: ans[i] = ans[i >> 1] + (i & 1), reusing the already-computed half.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/12-math-bits/047-counting-bits.js ./practice c 047