dsa · easy

Counting Bits

Given a non-negative integer n, return a list ans of length n + 1 where ans[i] is how many 1 bits appear in the binary writing of i, for every i from 0 through n.

Example

n = 5. Write each integer in binary and count the ones:

• 0 is 0 → 0 ones
• 1 is 1 → 1 one
• 2 is 10 → 1 one
• 3 is 11 → 2 ones
• 4 is 100 → 1 one
• 5 is 101 → 2 ones

So the answer is [0, 1, 1, 2, 1, 2].

n = 0 is only the value 0 → [0].

## Arguments - n — inclusive upper bound; return counts for 0..n

Constraints

0 <= n <= 10^5 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
5

Expected:
[0,1,1,2,1,2]

Example 2

Input:
0

Expected:
[0]

Example 3

Input:
2

Expected:
[0,1,1]

Open in the Dojo editor