Условие задачи

Дано неотрицательное целое число num. Необходимо для каждого числа в диапозоне 0 ≤ i ≤ num посчитать количество единиц в его бинарном представлении и вернуть массив этих данных.

пример 1

1
2

Input: 2
Output: [0,1,1]

пример 2

1
2

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

Follow up

• Легко найти решение со сложность O(n*sizeof(integer)). предлагается найти решение с линейной сложностью O(n).
• Сложность по памяти должна быть O(n)
• Сможете это сделать как супер профи? Без использования функции __builtin_popcountиз c++ или подобных в другом языке?

Решение

Динамика

Идея решения через динамическое программирование такая:

Создаем результирующий массив. Записываем значения для 0 и 1.

Создаем переменную где будем хранить следующую степень двойки cmp. Инициализиурем со значением 2 ( если мы до этого записали 0,1, и 1 если до этого записали только 0). Далее идем по результирующему массиву и записываем в текущую ячейку значение по индекс idx-cmp/2 + 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func countBits(num int) []int {
    k := make([]int,num+1)
    k[0] = 0
    if num == 0 {
        return k
    }
    cmp:=1
    for idx:=1; idx<=num; idx++ {
        if idx == 1 {
            k[1] = 1
            cmp = 2
            continue
        }
        if cmp == idx {
            cmp *=2
        }
        k[idx] = k[idx-cmp/2]+1
        
    }
    return k
}