Подсчет битов

Легкая
easy , bit manipulation , dynamic programming
06 September 2024

Описание задачи #

Дано число n.

Верните массив ans длиною n + 1, в котором значение каждого i-го элемента равно количеству единиц в двоичном представлении i. При этом i находится в диапазоне от 0 до n.

Ограничения #

Примеры #

  • Входные данные: n = 2

    Ответ: [0, 1, 1]

    Объяснение:

    Двоичные представления чисел.

    0 --> 0
1 --> 1
2 --> 10

  • Входные данные: n = 5

    Ответ: [0, 1, 1, 2, 1, 2]

    Объяснение:

    Двоичные представления чисел.

    0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Решение через подсчет популяции (Pop Count) #

В качестве решения можно воспользоваться способом подсчета популяции из задачи «Количество установленных битов».

Достаточно вызвать метод hammingWeight для подсчета веса Хэмминга в цикле от 0 до n.

Реализация #

  • package counting_bits

func hammingWeight(n int) int {
	count := 0

	for n != 0 {
		count++
		n &= n - 1
	}

	return count
}

func countBitsPopCount(n int) []int {
	res := make([]int, 0, n+1)

	for i := 0; i <= n; i++ {
		res = append(res, hammingWeight(i))
	}

	return res
}

  • const hammingWeight = (n: number): number => {
    let count = 0

    while (n != 0) {
        count++
        n &= n - 1
    }

    return count
}

export const countBitsPopCount = (n: number): number[] => {
    const res: number[] = []

    for (let i = 0; i <= n; i++) {
        res.push(hammingWeight(i))
    }

    return res
}

Оценка сложности #

По времени

Из решения предыдущей задачи мы знаем, что сложность метода hammingWeight равна O(1). Так как функция вызывается n раз, то итоговая сложность будет равна O(n).

По памяти

O(n) — так как выделяется память для хранения результирующего массива.

Решение через динамическое программирование #

Есть более простой способ решить задачу, но для этого надо знать формулу или постараться вывести закономерность в количестве единиц в битовом представлении числа. Таких формул есть несколько, но мы воспользуемся самой простой.

F(x) = F(x/2) + (x mod 2)

Это формула обозначает, что для получения количества единиц в битовом представлении числа x достаточно взять количество единиц в битовом представлении числа x/2 и прибавить к нему остаток от деления числа x на 2.

Теперь перефразируем эту формулу в битовых выражениях:

Общая идея

Мы можем представить число 𝑖 как результат добавления последнего бита к числу 𝑖 >> 1. Если последний бит — единица, то общее количество единиц увеличивается на 1 по сравнению с 𝑖 >> 1, если последний бит — ноль, то количество единиц остается тем же, что и у числа 𝑖 >> 1

Мы запускаем цикл подсчета единиц для каждого числа от 0 до n и каждый результат запоминаем в результирующий массив res. При этом на каждой итерации мы можем опираться на результаты вычислений предыдущих итераций и получать значение для i >> 1 из результирующего массива, так как оно уже было рассчитано раньше.

Реализация #

  • package counting_bits

func countBits(n int) []int {
	response := make([]int, n+1)

	for i := 0; i <= n; i++ {
		response[i] = response[i>>1] + (i & 1)
	}

	return response
}

  • export const countBits = (n: number): number[] => {
    const res: number[] = []

    for (let i = 0; i <= n; i++) {
        res[i] = (res[i >> 1] ?? 0) + (i & 1)
    }

    return res
}

Оценка сложности #

По времени

O(n) — так как нам надо провести вычисления n раз для каждого числа.

По памяти

O(n) — так как выделяется память для хранения результирующего массива.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >