Можно ли использовать функцию sum с генератором для подсчета количества последовательностей без подряд идущих единиц в Python

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

Понимаете ли вы, как sum работает с ленивыми итераторами, и видите ли, что короткий однострочник бывает экспоненциальным. Следом почти всегда просят решить быстрее, то есть динамическим программированием.

Как отвечать

Сначала уточните условие. Чаще всего это классика: сколько двоичных строк длины n не содержат двух единиц подряд.

Технически да, sum принимает любой итерируемый объект, а True складывается как 1:

sum('11' not in ''.join(p) for p in product('01', repeat=n))

Здесь product из itertools, генератор ленивый, и в памяти одновременно живёт одна строка. Но перебор идёт по 2^n вариантам, каждый проверяется за O(n). При n = 20 это около миллиона строк и терпимо, при n = 40 уже нет.

Хороший ответ строится на рекурренте. Пусть end0 и end1 это число допустимых строк, оканчивающихся на 0 и на 1. К строке на 0 можно дописать что угодно, к строке на 1 только 0, поэтому шаг выглядит так:

end0, end1 = end0 + end1, end0

Для n = 1 оба значения равны 1, ответ end0 + end1. Получается ряд 2, 3, 5, 8, то есть числа Фибоначчи со сдвигом. Это O(n) по времени и O(1) по памяти. Если спросят про огромные n, упомяните возведение матрицы 2×2 в степень за O(log n) и ответ по модулю: переполнения у int в Python нет, но числа растут и арифметика дорожает.

Если задача другая, например посчитать группы единиц в готовом списке, sum с генератором тоже подходит: sum(1 for i, x in enumerate(a) if x == 1 and (i == 0 or a[i - 1] != 1)). Один проход, без промежуточных списков.

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

Не уточняют условие и решают другую задачу. Подсчёт групп единиц в массиве и подсчёт допустимых строк длины n звучат похоже, а решения у них разные.

Оборачивают генератор в квадратные скобки, превращая его в списковое включение. Результат тот же, но весь список сначала строится в памяти, и на переборе это заметно.

Останавливаются на переборе и называют его оптимальным, раз он в одну строку. Интервьюер ждёт, что вы сами назовёте сложность O(n·2^n) и предложите линейное решение.