1318. Counting Bits — DP + Bit

Given a non-negative integer n, return an array of length n+1 where the i-th entry is the number of set bits in i, for i from 0 to n.

Input: A JSON object {"n": <non-negative integer>}.

Output: Return the array [popcount(0), popcount(1), ..., popcount(n)].

Examples

Example 1

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

Example 2

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