Problema
Inizia la sequenza con 1 e 2. Ogni termine successivo è la somma dei due precedenti. Considera solo i termini di valore pari che non superano il limite, poi somma questi valori.
Implementa even_fibonacci_sum(limit).
Input
limit: Il valore massimo che un termine può avere per essere incluso.
Output
Restituisci la somma, oppure 0 se non ci sono termini idonei.
Vincoli
0 ≤ limit ≤ 10¹⁵. Il risultato rientra in un intero con segno a 64 bit.
Esempi
Input:
limit = 50
Output atteso:
expected = 44Input:
long long limit = 50;
Output atteso:
long long expected = 44;Input:
long limit = 50;
Output atteso:
long expected = 44;Spiegazione
I termini pari sono 2, 8 e 34. La loro somma è 44.
Input:
limit = 1
Output atteso:
expected = 0Input:
long long limit = 1;
Output atteso:
long long expected = 0;Input:
long limit = 1;
Output atteso:
long expected = 0;Spiegazione
Il primo termine pari è 2, che supera il limite.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ti servono solo i termini pari di Fibonacci, non tutta la sequenza.
Suggerimento 2
Genera la sequenza finché il termine successivo supera il limite e somma i termini validi.
Suggerimento 3
Fai attenzione al caso in cui il limite stesso sia un termine di Fibonacci.
Complessità attesa
tempo O(log limit), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.