Counting Bits

Difficulty: Medium · Topic: Bit manipulation

Return an array ans of length n + 1 where ans[i] is the number of set bits (1s) in i. The DP insight: i has the same bits as i >> 1 plus the lowest bit, so ans[i] = ans[i >> 1] + (i & 1).

Examples

counting_bits(2)
→ [0,1,1]

0→0, 1→1, 2(10)→1.

counting_bits(5)
→ [0,1,1,2,1,2]

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.