338. Counting Bits

Practice Counting Bits for free on NudgeCode: Easy, Bit Manipulation pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i. Try to do it in one O(n) pass.

Example

n = 2  ->  [0,1,1]
n = 5  ->  [0,1,1,2,1,2]

Constraints

• 0 <= n <= 10^5