Какое условие выполняется для битовых последовательностей без подряд идущих единиц

Что проверяют

Видите ли вы за условием и битовый трюк, и связь с числами Фибоначчи. Обычно это разминка перед задачей: проверить число, посчитать такие последовательности длины n или сгенерировать их все. Следом просят оценить сложность и объяснить, откуда берётся рекуррентность.

Как отвечать

Условие: никакие две единицы не стоят рядом. Для числа это проверяется одной операцией x & (x >> 1) == 0. Сдвиг ставит каждый бит напротив соседа, и если где-то единица совпала с единицей, результат ненулевой: 5 (101) проходит, 6 (110) нет. В Python & связывает сильнее, чем ==, так что лишние скобки не нужны.

Количество таких строк длины n подчиняется рекуррентности Фибоначчи. Строка оканчивается либо на 0, и тогда перед ним любая допустимая строка длины n-1, либо на 1, и тогда перед единицей обязательно 0, то есть окончание 01 и допустимая строка длины n-2. Отсюда f(n) = f(n-1) + f(n-2), f(1) = 2, f(2) = 3, а в обычной нумерации Фибоначчи это F(n+2).

def count(n: int) -> int:
    end0, end1 = 1, 1
    for _ in range(n - 1):
        end0, end1 = end0 + end1, end0
    return end0 + end1

Что стоит проговорить:

• сложность: O(n) по времени и O(1) по памяти. Для огромных n есть возведение матрицы в степень за O(log n);
• целые в Python: переполнения нет, но числа растут экспоненциально, и арифметика с ними перестаёт быть бесплатной;
• генерация: перебор всех 2**n строк с фильтром работает, но рекурсивное построение, где после 1 сразу ставится 0, выдаёт только нужные строки, а их порядка 1.618**n.

Где спотыкаются

Пишут рекурсию f(n-1) + f(n-2) без мемоизации и получают экспоненциальное время. Помогает functools.cache или цикл, к тому же глубокая рекурсия упрётся в лимит около 1000 вызовов.

Ошибаются с базой: берут f(1) = 1, как в классическом Фибоначчи, и весь ответ сдвигается на индекс.

Проверяют через строку "11" in bin(x). Работает, но это лишнее создание строки, а на собеседовании ждут побитовое решение.