Counting Bits

Условие

Дано целое число n. Вернуть массив ans длины n + 1, где для каждого i от 0 до n значение ans[i] — это количество единиц в двоичном представлении числа i.

Примеры

Input: n = 2

Output: [0, 1, 1]

Explanation:

0 --> 0

1 --> 1

2 --> 10

Input: n = 5

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

Explanation:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101

Решение

fun countBits(n: Int): IntArray {
    val ans = IntArray(n + 1) // Создаем массив для хранения количества единиц

    for (i in 1..n) {
        // Количество единиц в числе i получается из числа i / 2 (i shr 1)
        // Плюс добавляем 1, если младший бит i равен 1 (i and 1)
        ans[i] = ans[i shr 1] + (i and 1)
    }
    
    return ans // Возвращаем результат
}

Временная сложность

O(n), где n — входное значение. Мы вычисляем значение для каждого числа от 0 до n за O(1).

Пространственная сложность

O(n), поскольку создаем массив ans длиной n + 1 для хранения результатов.