Строка Гугола
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Рекурсия и перебор
- Математика
Определим строки из нулей и единиц: S1 = "0", а S(N) = S(N-1) + "0" + инверсия(разворот(S(N-1))), где разворот записывает строку задом наперёд, а инверсия меняет каждый 0 на 1 и наоборот. Получаются S2 = "001", S3 = "0010011", S4 = "001001100011011" и так далее. Каждая строка является началом следующей, поэтому у последовательности есть предельная бесконечная строка. Верните её k-й символ (нумерация с 1) как число 0 или 1.
Ограничения: 1 ≤ k ≤ 9·10^15.
Пример: 3 → 1 (в S2 = "001" третий символ — 1); 10 → 0.
Источник: Coding Competitions Archive, kickstart/2015/round_a/googol_string · © Google LLC · Apache-2.0 · условие переведено и дополнено
Решить онлайнБесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).