Counting Bits

Q: Какова временная сложность подсчёта битов?

Лучшее решение работает за время O(n): каждая из n+1 записей получается из одной предыдущей записи с помощью одного сложения. Подсчёт битов каждого числа по одному занимает O(n log n), потому что число не больше n имеет примерно log2 n двоичных цифр. Оба решения используют O(1) дополнительной памяти помимо выходного массива.

Q: Почему работает bits[i] = bits[i >> 1] + (i & 1)?

i >> 1 — это i без последней двоичной цифры, а i & 1 — эта удалённая цифра. Количество единиц в i равно количеству единиц в меньшем числе плюс последняя цифра. Для 11, то есть 1011 , меньшее число — 5 ( 101 , две единицы), а последняя цифра — 1, поэтому в 11 три единицы.

Q: Существует ли ещё одна рекуррентная формула за O(n) для подсчёта битов?

Да. i & (i-1) очищает младший бит 1 числа i , поэтому bits[i] = bits[i & (i-1)] + 1 для каждого i , равного 1 или больше. Для 12 ( 1100 ) выражение 12 & 11 равно 8 ( 1000 ), в котором одна единица, значит, в 12 их две. Этот способ такой же быстрый, как правило со сдвигом, и использует то же заполнение слева направо.

Q: Могу ли я использовать встроенную функцию подсчёта единичных битов?

В большинстве языков такая функция есть, например Integer.bitCount в Java или __builtin_popcount в C и C++, и её вызов для каждого числа даёт правильный ответ. Обычно на собеседованиях просят решить задачу без неё, потому что суть задачи — повторно использовать уже вычисленные ответы. Эта рекуррентная формула также работает в языках, где такой функции нет.

ЛегкоБитовые операции Динамическое программирование

+10

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

Функция

countBits(n: integer) → integer-array

ninteger: последнее число для отсчёта, 0 или больше
Возвращаетinteger-array: массив из n+1 счётчиков, где элемент i — это количество битов 1 в числе i

Ограничения

0 ≤ n ≤ 2 × 10⁴

Примеры

Ввод: n = 2
Вывод: [0, 1, 1]
Пояснение: В двоичной системе 0 — это 0, 1 — это 1, а 2 — это 10. То есть сначала ни одной 1, затем одна, затем одна.

Ввод: n = 5
Вывод: [0, 1, 1, 2, 1, 2]
Пояснение: 3 — это 11, а 5 — 101, в каждом по две единицы, тогда как 4 — это 100 с одной единицей. Если добавить 0, 1 и 2 из первого примера, количество единиц для чисел от 0 до 5 будет равно 0, 1, 1, 2, 1, 2.

+15 скрытых тестов при отправке

Дополнительный вопрос

Сможешь заполнить весь массив за время O(n), не используя встроенную функцию для подсчёта битов и не подсчитывая каждый номер с нуля?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Подсчитывать единицы в двоичной записи каждого числа по отдельности можно, но это приводит к повторению работы. 13 — это 1101, а 6 — это 110: биты числа 13 — это биты числа 6 с ещё одной цифрой в конце. Если заполнять ответы в порядке возрастания, нужное количество для i уже есть в массиве, и для каждой записи требуется одно сложение.

Подсчитайте биты каждого числа

Идея

Для каждого числа от 0 до n напрямую подсчитай количество его битов 1. Младший бит числа x — это x & 1. Добавь его к счётчику, затем сдвинь x вправо с помощью x >> 1, чтобы следующий бит стал младшим. Остановись, когда x достигнет 0.

Для 13, то есть 1101, справа налево получаются биты 1, 0, 1, 1, поэтому количество равно 3. Для каждого числа требуется по одному шагу на двоичную цифру, а число до n содержит примерно log2 n цифр.

Итого весь запуск выполняется за O(n log n). Для n = 2 × 10^4 это примерно 20 000 × 15 = 300 000 шагов, что укладывается по времени. Но при этом часть работы выполняется повторно: при подсчёте 13 повторяется каждый шаг, уже выполненный для 6. Пространственная сложность — O(1), не считая выходного массива.

Алгоритм

Создайте пустой список результатов.
Для каждого i от 0 до n установите count равным 0, а x — равным i.
Пока x больше 0, добавляйте x & 1 к count и сдвигайте x вправо на один разряд.
Добавьте count в список результатов.
Верните список результатов.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Увеличьте число вдвое

Идея

Сдвиг i вправо на один разряд удаляет его последнюю двоичную цифру. Поэтому в i ровно столько же единичных битов, сколько в i >> 1, плюс ещё один, если последняя цифра равна 1. Эта последняя цифра — i & 1, отсюда правило bits[i] = bits[i >> 1] + (i & 1).

Для каждого i, равного 1 или больше, i >> 1 меньше, чем i. Если заполнять массив слева направо, начиная с bits[0] = 0, искомая запись уже всегда будет заполнена. Это динамическое программирование: каждый ответ строится на основе меньшего.

Для n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Для каждой записи нужны один сдвиг, одна операция AND и одно сложение, поэтому время работы — O(n), а дополнительная память, помимо выходных данных, не требуется.

Алгоритм

Создай массив bits из n+1 нулей. bits[0] остаётся равным 0.
Для i от 1 до n присвой bits[i] значение bits[i >> 1] + (i & 1).
Верни bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Ловушки и крайние случаи

Правило умещается в одну строку, поэтому ошибки скрываются в деталях.

Массив содержит n+1 элементов, а не n. При n = 0 ответ — [0]: один элемент для числа 0.
Приоритет операторов. В Python, C, Java и JavaScript оператор + имеет более высокий приоритет, чем &, поэтому выражение bits[i >> 1] + i & 1 читается как (bits[i >> 1] + i) & 1. Не убирай скобки вокруг (i & 1).
Обращение к bits[i-1] вместо bits[i >> 1]. У соседних чисел нет простого общего правила: 7 — это 111, где три единицы, а 8 — 1000, где одна.
В Lua и R массивы начинаются с 1, поэтому количество для i находится по индексу i+1, а обращение к i >> 1 — по индексу floor(i/2) + 1. В Lua среды запуска нет оператора сдвига, поэтому дели пополам с помощью math.floor(i / 2).
Преобразование каждого числа в двоичную строку и подсчёт символов 1 дают правильный ответ, но при этом для каждого числа создаётся новая строка.

Частые вопросы4

Какова временная сложность подсчёта битов?

Лучшее решение работает за время O(n): каждая из n+1 записей получается из одной предыдущей записи с помощью одного сложения. Подсчёт битов каждого числа по одному занимает O(n log n), потому что число не больше n имеет примерно log2 n двоичных цифр. Оба решения используют O(1) дополнительной памяти помимо выходного массива.

Почему работает bits[i] = bits[i >> 1] + (i & 1)?

i >> 1 — это i без последней двоичной цифры, а i & 1 — эта удалённая цифра. Количество единиц в i равно количеству единиц в меньшем числе плюс последняя цифра. Для 11, то есть 1011, меньшее число — 5 (101, две единицы), а последняя цифра — 1, поэтому в 11 три единицы.

Существует ли ещё одна рекуррентная формула за O(n) для подсчёта битов?

Да. i & (i-1) очищает младший бит 1 числа i, поэтому bits[i] = bits[i & (i-1)] + 1 для каждого i, равного 1 или больше. Для 12 (1100) выражение 12 & 11 равно 8 (1000), в котором одна единица, значит, в 12 их две. Этот способ такой же быстрый, как правило со сдвигом, и использует то же заполнение слева направо.

Могу ли я использовать встроенную функцию подсчёта единичных битов?

В большинстве языков такая функция есть, например Integer.bitCount в Java или __builtin_popcount в C и C++, и её вызов для каждого числа даёт правильный ответ. Обычно на собеседованиях просят решить задачу без неё, потому что суть задачи — повторно использовать уже вычисленные ответы. Эта рекуррентная формула также работает в языках, где такой функции нет.

Python

def countBits(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

n = 2

Ожидается

[0, 1, 1]