Fibonacci Matrix Power

Problem

Compute the n-th Fibonacci number F(n) with F(0) = 0 and F(1) = 1 using fast exponentiation of the matrix [[1, 1], [1, 0]].

Since the matrix raised to n has F(n) in its top-right corner, return that entry.

Hint

Binary exponentiation makes F(n) computable in O(log n) matrix multiplies.

case 1

in: [0]

expected: 0

case 2

in: [1]

expected: 1

case 3

in: [10]

expected: 55

case 4

in: [20]

expected: 6765

Starter codePython

def fibonacci_matrix(n):
    # Your code here
    pass

4 test cases · run your code against them in the editor