Fácil 0 resueltos 0% de aceptación

Lucas Numbers

Return the nth Lucas number, the Fibonacci-like sequence that starts 2, 1.

Lo que aprenderás

  • Compute a Fibonacci-like sequence
  • Use the right starting values
  • Avoid computing one term past the answer

Problema

Ver traducción

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.