A binary counter shows each value with one lamp per bit; a lamp is lit when its bit is 1. For every value 0, 1, ..., n report how many lamps are lit. Return the list of n + 1 counts.
Examples
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 0, 1, 10, 11, 100, 101 in binary.
Input: n = 0
Output: [0]
Constraints
0 <= n <= 10**5- Target complexity: O(n) total, without converting every number to a string.
Goals
- Relate the bit count of i to the bit count of i >> 1
- Build the whole table in one linear pass