Crie uma função que receba um número n e retorne os quatro últimos dígitos do número de Fibonacci na posição n.
Neste desafio, o número n fornecido pode ser enorme (na casa dos bilhões). Portanto, um algoritmo que execute n iterações não terminará dentro do tempo disponível. Por isso, você precisa descobrir o algoritmo que encontra a resposta em O(log n).
fibonacci(6) ➞ 8
fibonacci(10) ➞ 55
fibonacci(10000000) ➞ 6875
fibonacci(12345678901) ➞ 7401Os números de Fibonacci são definidos da seguinte forma:
f(0) = 0, f(1) = 1, and f(i) = f(i−1) + f(i−2)