Tutte le sfide
Facile 0 risolte 0% di accettazione

Il primo numero di Fibonacci con n cifre

Trova la posizione del primo numero di Fibonacci che ha n cifre.

Cosa imparerai

  • Sommare due array di cifre
  • Generare i termini di Fibonacci senza overflow
  • Fermarsi al primo termine che soddisfa una condizione

Problema

La successione di Fibonacci inizia con F(1) = 1, F(2) = 1, e ogni termine successivo è la somma dei due precedenti: 1, 1, 2, 3, 5, 8, 13, 21, ... Trova il punto in cui la successione raggiunge per la prima volta n cifre decimali. I termini superano presto gli interi a 64 bit, quindi, se il tuo linguaggio non ha interi grandi, sommali come array di cifre.

Implementa fibonacci_with_n_digits(n).

Input

n: il numero di cifre.

Output

Restituisci l'indice i del primo termine F(i) con almeno n cifre. Per n = 1 la risposta è 1.

Vincoli

1 ≤ n ≤ 1000

Esempi

Esempio 1
Input:
n = 2

Output atteso:
expected = 7
Input:
long long n = 2;

Output atteso:
long long expected = 7;
Input:
long n = 2;

Output atteso:
long expected = 7;

Spiegazione

F(6) = 8 ha una cifra e F(7) = 13 ne ha due, quindi la risposta è 7.

Esempio 2
Input:
n = 4

Output atteso:
expected = 17
Input:
long long n = 4;

Output atteso:
long long expected = 17;
Input:
long n = 4;

Output atteso:
long expected = 17;

Spiegazione

F(16) = 987 e F(17) = 1597, quindi la risposta è 17.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Tieni solo gli ultimi due termini.

Suggerimento 2

Memorizza ogni termine come cifre e sommali con i riporti.

Suggerimento 3

Conta l'indice man mano, partendo da F(1) = 1.

Complessità attesa

tempo O(n²), spazio aggiuntivo O(n)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.