1125. Counting Bits — Number of 1s for 0 to N

Given an integer n, return an array of length n+1 where the i-th element is the number of set bits (1s) in the binary representation of i. The input is JSON {n}.

Input: JSON {n}.

Output: Array — the set-bit count for each i from 0 to n.

Examples

Input: {"n":2}
Output: [0,1,1]
Explanation: 0->0, 1->1, 2->1.

Input: {"n":5}
Output: [0,1,1,2,1,2]
Explanation: Set-bit counts up to 5.

Input: {"n":0}
Output: [0]
Explanation: Only zero.

Constraints

• 0<=n<=10^5

Asked by