Problema
The Lucas numbers follow the same rule as the Fibonacci numbers, each term being the sum of the two before it, but they start differently: L(0) = 2 and L(1) = 1. The sequence goes 2, 1, 3, 4, 7, 11, 18, 29, …
Implement lucas_numbers(n).
Input
n: The index of the term, starting at 0.
Output
Return L(n).
Restricciones
0 ≤ n ≤ 90
Ejemplos
Entrada:
n = 6
Salida esperada:
expected = 18
Entrada:
long long n = 6;
Salida esperada:
long long expected = 18;
Entrada:
long n = 6;
Salida esperada:
long expected = 18;
Explicación
The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.
Entrada:
n = 0
Salida esperada:
expected = 2
Entrada:
long long n = 0;
Salida esperada:
long long expected = 2;
Entrada:
long n = 0;
Salida esperada:
long expected = 2;
Explicación
The sequence starts with L(0) = 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Keep the current and next terms in two variables.
Pista 2
The only difference from Fibonacci is the start: 2 and 1.
Pista 3
For n = 90 the next term would not fit in 64 bits, so stop the loop at n.
Complejidad esperada
O(n) time, O(1) extra space
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.