Description
Given an integer n, return an array ans of length n+1 where ans[i] is the number of 1's in the binary representation of i.
Examples
Input:
n = 5Output:
[0,1,1,2,1,2]Explanation:
Counting 1-bits in binary: 0(0)=0, 1(1)=1, 2(10)=1, 3(11)=2, 4(100)=1, 5(101)=2. Pattern: ans[i] = ans[i>>1] + (i&1).
Input:
n = 0Output:
[0]Explanation:
For n=0, only the number 0 is counted. The binary representation of 0 is '0', which contains zero 1's.
Input:
n = 7Output:
[0,1,1,2,1,2,2,3]Explanation:
For n=7: 0=0 (0 ones), 1=1 (1 one), 2=10 (1 one), 3=11 (2 ones), 4=100 (1 one), 5=101 (2 ones), 6=110 (2 ones), 7=111 (3 ones)
Constraints
- •
0 ≤ n ≤ 10⁵