Сложность: 🟢 Легкая
ℹ️ Описание
Дано число n.
Верните массив ans длиною n + 1, в котором значение каждого i-го элемента равно количеству единиц в двоичном представлении i.
При этом i находится в диапазоне от 0 до n.
⚠️ Ограничения
— Значение n находится в диапазоне от 1 до 10^5
1️⃣ Пример
Входные данные: n = 2
Ответ: [0, 1, 1]
Объяснение:
Двоичные представления чисел.
0 --> 0
1 --> 1
2 --> 10
2️⃣ Пример
Входные данные: 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.
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
}
✅ Решение через динамическое программирование
Есть более простой способ решить задачу, но для этого надо знать формулу или постараться вывести закономерность в количестве единиц в битовом представлении числа. Таких формул есть несколько, но мы воспользуемся самой простой.
F(x) = F(x/2) + (x mod 2)
Это формула обозначает, что для получения количества единиц в битовом представлении числа x достаточно взять количество единиц в битовом представлении числа x/2 и прибавить к нему остаток от деления числа x на 2.
Теперь перефразируем эту формулу в битовых выражениях:
операция x / 2 эквивалентна битовому сдвигу на единицу вправо, то есть x >> 1
операция x mod 2 эквивалентна получению младшего бита, то есть x & 1
Общая идея
Мы можем представить число 𝑖 как результат добавления последнего бита к числу 𝑖 >> 1. Если последний бит — единица, то общее количество единиц увеличивается на 1 по сравнению с 𝑖 >> 1, если последний бит — ноль, то количество единиц остается тем же, что и у числа 𝑖 >> 1
Мы запускаем цикл подсчета единиц для каждого числа от 0 до n и каждый результат запоминаем в результирующий массив res. При этом на каждой итерации мы можем опираться на результаты вычислений предыдущих итераций и получать значение для i >> 1 из результирующего массива, так как оно уже было рассчитано раньше.
Посмотреть реализацию в блоге
#bit_manipulation #easy