A generative-art page sizes its spiral tiles with Fibonacci numbers: F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2). A stress test asks for tiles very far along the sequence.
Write fibonacciFar(n) that returns F(n) modulo 1000000007. n can be up to 10^15, so a loop over every step is too slow.
Input: n = 10 Output: 55
The sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
Input: n = 0 Output: 0
F(0) = 0 by definition.
0 <= n <= 10^15Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #659 Fibonacci Far Ahead. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.