Efficient Nth Term Computation | Dataford Interview Questions

A Zoho Analytics computation may need to evaluate very large indexed sequence values without iterating through every preceding term. Given n and a positive modulus, return the nth Fibonacci number modulo that modulus using an algorithm faster than linear time.

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

Use the fast-doubling identities:

F(2k) = F(k) * (2F(k + 1) - F(k))
F(2k + 1) = F(k)^2 + F(k + 1)^2

Formal Specification

Implement fibonacci_mod(n, mod), where n and mod are integers. Return an integer equal to F(n) % mod. The algorithm must run in O(log n) time.

Constraints

0 <= n <= 10^18
1 <= mod <= 10^9 + 7
Return an integer equal to F(n) modulo mod
The required time complexity is O(log n)

Function Signature

def fibonacci_mod(n, mod):

Your question is Efficient Nth Term Computation. Start with the requirements in the Question tab.

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

Problem