Optimal Fibonacci Computation

Coding · Medium · Free problem
Implement a function that computes the $n$-th Fibonacci number, where $F(0) = 0$, $F(1) = 1$, and $F(n) = F(n-1) + F(n-2)$ for $n \geq 2$. Your solution should achieve $O(\log n)$ time complexity. **Constraints:** - $0 \leq n \leq 10^{18}$ - Return the exact value of $F(n)$ (assume arbitrary-precision integers) **Examples:** - Input: `n = 0` -> Output: `0` - Input: `n = 1` -> Output: `1` - Input: `n = 10` -> Output: `55` - Input: `n = 50` -> Output: `12586269025`

Open the full interactive solver, hints, and worked solution →