Problema
A sequência de Fibonacci começa com F(1) = 1, F(2) = 1, e cada termo seguinte é a soma dos dois anteriores: 1, 1, 2, 3, 5, 8, 13, 21, ... Descubra em que ponto a sequência chega pela primeira vez a n dígitos decimais. Os termos logo passam do limite dos inteiros de 64 bits, então some-os como arrays de dígitos se a sua linguagem não tiver inteiros grandes.
Implemente fibonacci_with_n_digits(n).
Entrada
n: a quantidade de dígitos.
Saída
Retorne o índice i do primeiro termo F(i) com pelo menos n dígitos. Para n = 1, a resposta é 1.
Restrições
1 ≤ n ≤ 1000
Exemplos
Entrada:
n = 2
Saída esperada:
expected = 7
Entrada:
long long n = 2;
Saída esperada:
long long expected = 7;
Entrada:
long n = 2;
Saída esperada:
long expected = 7;
Explicação
F(6) = 8 tem um dígito e F(7) = 13 tem dois, então a resposta é 7.
Entrada:
n = 4
Saída esperada:
expected = 17
Entrada:
long long n = 4;
Saída esperada:
long long expected = 17;
Entrada:
long n = 4;
Saída esperada:
long expected = 17;
Explicação
F(16) = 987 e F(17) = 1597, então a resposta é 17.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Guarde só os dois últimos termos.
Dica 2
Armazene cada termo como dígitos e some-os com "vai um".
Dica 3
Conte o índice à medida que avança, começando em F(1) = 1.
Complexidade esperada
tempo O(n²), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.