Последовательность Фибоначчи начинается с F(1) = 1, F(2) = 1, и каждый следующий член равен сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, ... Найдите, где в последовательности впервые встречается число из n десятичных цифр. Члены быстро перестают помещаться в 64-битные целые, поэтому, если в вашем языке нет длинной арифметики, складывайте их как массивы цифр.
Реализуйте fibonacci_with_n_digits(n).
Входные данные
n: количество цифр.
Выходные данные
Верните номер i первого члена F(i), в котором не меньше n цифр. Для n = 1 ответ равен 1.
Ограничения
1 ≤ n ≤ 1000
Примеры
Ввод:
n = 2
Ожидаемый вывод:
expected = 7
Ввод:
long long n = 2;
Ожидаемый вывод:
long long expected = 7;
Ввод:
long n = 2;
Ожидаемый вывод:
long expected = 7;
Пояснение
В F(6) = 8 одна цифра, а в F(7) = 13 две, поэтому ответ 7.
Ввод:
n = 4
Ожидаемый вывод:
expected = 17
Ввод:
long long n = 4;
Ожидаемый вывод:
long long expected = 17;
Ввод:
long n = 4;
Ожидаемый вывод:
long expected = 17;
Пояснение
F(16) = 987, а F(17) = 1597, поэтому ответ 17.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Храните только два последних члена.
Подсказка 2
Храните каждый член как цифры и складывайте их с переносами.
Подсказка 3
Считайте номер по ходу, начиная с F(1) = 1.
Ожидаемая сложность
время O(n²), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.