Counting Bits
Easy · dynamic programming
Written in binary, every non-negative integer is a row of 0 and 1 digits (bits). Given a non-negative integer n, return a list of length n + 1 where the value at position i is the number of bits equal to 1 in the binary form of i, for every i from 0 to n.
For example, 5 is 101 in binary, so position 5 of the list holds 2.
Examples
Example 1
Input: n = 2
Output: [0, 1, 1]
0 is 0, 1 is 1 and 2 is 10 in binary, which have zero, one and one bits equal to 1.
Example 2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
3 is 11 and 5 is 101, so they hold 2; 4 is 100, so it holds 1.
Example 3
Input: n = 0
Output: [0]
Constraints
- 0 <= n <= 10^4