Разбор задачи «Светящиеся панели»

Идея задачи

Для каждого числа от 0 до n нужно посчитать количество единиц в его двоичной записи.

Например:

• 0 → 0 → 0 единиц
• 1 → 1 → 1 единица
• 2 → 10 → 1 единица
• 3 → 11 → 2 единицы
• 4 → 100 → 1 единица
• 5 → 101 → 2 единицы

Нужно вывести ответы сразу для всех чисел от 0 до n.

Наивный подход

Самое очевидное решение — для каждого числа отдельно смотреть на его двоичную запись и считать количество единиц.

Например, можно многократно делить число на 2 или использовать битовые операции.

Тогда для одного числа это займет O(log n), потому что в двоичной записи примерно log n бит. А для всех чисел от 0 до n получится около O(n log n).

Такое решение уже может пройти при небольших ограничениях, но задачу можно решить лучше — за O(n).

Главное наблюдение

Посмотрим на число i.

Если сдвинуть его вправо на один бит, то мы просто отбросим последний двоичный разряд.

Например:

• 13 = 1101
• 13 >> 1 = 110 = 6

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

Последний бит можно получить так:

• i & 1

Это выражение равно:

• 0, если число четное
• 1, если число нечетное

Значит,

количество единиц в числе i

количество единиц в числе i >> 1 + последний бит числа i

Получаем формулу:

dp[i] = dp[i >> 1] + (i & 1)

Это и есть основа решения.

Почему формула верна

Рассмотрим число i в двоичной записи.

Случай 1. Последний бит равен 0

Например:

• 10 = 1010
• 10 >> 1 = 101

Когда мы убираем последний ноль, количество единиц не меняется. Значит:

dp[10] = dp[5] + 0

Случай 2. Последний бит равен 1

Например:

• 11 = 1011
• 11 >> 1 = 101

После сдвига вправо мы убрали последнюю единицу. Значит, у исходного числа единиц на одну больше:

dp[11] = dp[5] + 1

Оба случая сразу объединяются в одну формулу:

dp[i] = dp[i >> 1] + (i & 1)

Как будем считать ответы

Создадим массив dp, где:

• dp[i] — количество единиц в двоичной записи числа i

База:

• dp[0] = 0

Дальше идем по числам от 1 до n и считаем:

dp[i] = dp[i >> 1] + (i & 1)

Поскольку число i >> 1 всегда меньше i, нужное значение уже будет посчитано раньше.

Небольшой пример

Пусть n = 5.

Тогда:

• dp[0] = 0
• dp[1] = dp[0] + 1 = 1
• dp[2] = dp[1] + 0 = 1
• dp[3] = dp[1] + 1 = 2
• dp[4] = dp[2] + 0 = 1
• dp[5] = dp[2] + 1 = 2

Ответ:

0 1 1 2 1 2

Пошаговый алгоритм

1. Считать число n.
2. Создать массив dp длины n + 1.
3. Записать dp[0] = 0.

4. Для каждого i от 1 до n вычислить:

   • dp[i] = dp[i >> 1] + (i & 1)
5. Вывести массив dp.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }

    for (int i = 0; i <= n; i++) {
        cout << dp[i];
        if (i < n) cout << ' ';
    }
    cout << '\n';

    return 0;
}

Решение на Python

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = dp[i >> 1] + (i & 1)

print(*dp)

Разбор кода

Что означает i >> 1

Это сдвиг вправо на 1 бит.

Примеры:

• 6 = 110, после сдвига получим 11 = 3
• 5 = 101, после сдвига получим 10 = 2

То есть это почти то же самое, что целочисленно поделить на 2.

Что означает i & 1

Это операция побитового И.

Она позволяет проверить последний бит числа:

• если число четное, результат 0
• если число нечетное, результат 1

Например:

• 6 = 110, 6 & 1 = 0
• 7 = 111, 7 & 1 = 1

Почему можно идти слева направо

Потому что при вычислении dp[i] нам нужно значение dp[i >> 1], а число i >> 1 всегда меньше i. Значит, оно уже было посчитано раньше.

Сложность

По времени

Мы проходим по всем числам от 1 до n один раз. На каждом шаге делаем только несколько простых операций.

Итого:

• O(n)

По памяти

Мы храним массив из n + 1 чисел.

Итого:

• O(n)

Частые ошибки

1. Считать количество единиц отдельно для каждого числа

Такое решение обычно работает медленнее, чем нужно.

2. Забыть про число 0

У числа 0 в этой задаче количество единиц равно 0.

3. Неправильно понять i >> 1

Это не удаление единицы, а удаление последнего бита вообще. Если последний бит был 0, число единиц не меняется. Если последний бит был 1, число единиц уменьшается на 1.

4. Ошибка в выводе

Нужно вывести ответы для всех чисел от 0 до n, а не только для числа n.

Альтернативная формула

Иногда используют еще одну полезную формулу:

dp[i] = dp[i & (i - 1)] + 1

Выражение i & (i - 1) убирает у числа последнюю единицу.

Например:

• 12 = 1100
• 11 = 1011
• 12 & 11 = 1000 = 8

Тогда:

• dp[12] = dp[8] + 1

Это тоже правильное и хорошее решение. Но формула

dp[i] = dp[i >> 1] + (i & 1)

обычно проще для первого знакомства с задачей.

Вывод

В этой задаче важно заметить связь между числом и его двоичной записью после сдвига вправо.

Ключевая идея очень компактная:

dp[i] = dp[i >> 1] + (i & 1)

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

Это хороший пример задачи, где одна короткая формула позволяет перейти от наивного решения к очень эффективному.