Número de Fibonacci

Problema

A sequência de Fibonacci começa com 0, 1 e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 e F(1) = 1.

Implemente fibonacci(n).

n: A posição na sequência.

Retorne F(n).

0 ≤ n ≤ 90

Exemplo 1

Entrada:
n = 10

Saída esperada:
expected = 55

Entrada:
long long n = 10;

Saída esperada:
long long expected = 55;

Entrada:
long n = 10;

Saída esperada:
long expected = 55;

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.

Exemplo 2

Entrada:
n = 0

Saída esperada:
expected = 0

Entrada:
long long n = 0;

Saída esperada:
long long expected = 0;

Entrada:
long n = 0;

Saída esperada:
long expected = 0;

Por definição, F(0) = 0.

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Os dois primeiros valores são fixos, então comece pelos casos base.

Dica 2

Construa os próximos valores a partir dos dois anteriores em vez de recalcular recursivamente.

Dica 3

Use uma abordagem iterativa para evitar trabalho repetido e recursão profunda.

Complexidade esperada

tempo O(n), espaço extra O(1)

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.