Fibonacci With Complexity

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Fibonacci With Complexity. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

CAE engineering simulation workflows may request sequence values at extremely large indices. Implement fibonacci(n, mod) to return the nth Fibonacci number modulo mod, using an algorithm that remains efficient when n is as large as 10^18.

The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.

Formal Specification

Input: Two integers, n and mod.
Output: An integer equal to F(n) % mod.
Use fast doubling identities to avoid constructing all preceding Fibonacci values.
The input satisfies n >= 0 and mod >= 2.

Constraints

0 <= n <= 10^18
2 <= mod <= 10^9
The result must equal F(n) modulo mod
The algorithm must run in O(log n) time
Do not generate all Fibonacci values up to n

Function Signature

def fibonacci(n, mod):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output