Counting Bits

Sizga butun son n berilgan. Uzunligi n + 1 bo'lgan ans massivini qaytaring, bunda ans[i] qiymati i sonining ikkilik (binary) ko'rinishidagi 1 larning sonidir.

Yechimingiz O(n) vaqt murakkabligida va O(n) dan kam qo'shimcha xotirada ishlashi kerak.

func solve(n int) []int {
    // ...
}

Misollar

Input: n = 2
Output: [0,1,1]
Tushuntirish:
0 -> 0b0 -> 0 ta '1'
1 -> 0b1 -> 1 ta '1'
2 -> 0b10 -> 1 ta '1'

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Input: n = 0
Output: [0]

Input: n = 8
Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]

Maslahatlar

1. Har bir sonni alohida bitlar sonini hisoblash shart emas — oldin hisoblangan kichikroq sonlar natijasidan foydalanib dinamik dasturlash qo'llash mumkin.
2. i sonining bitlar soni i>>1 (2 ga bo'lingan qismi) uchun avval hisoblangan natijaga, i ning eng oxirgi biti (i&1) qo'shilgan holda topiladi: ans[i] = ans[i>>1] + (i&1).