Loading…

mediumMath GeometrySometimes asked

Matrix Exponentiation (Fibonacci)

Q: How do you solve Matrix Exponentiation (Fibonacci) using the Iterative DP (Baseline) approach?

When to use it: Mention first — it's the obvious O(n) solution and is the right answer for small n. It anchors the O(n) cost the matrix method beats. Translate the recurrence straight into a loop. Hold the previous two Fibonacci numbers in two variables and roll them forward. **How it works.** Start with `a = F₀ = 0` and `b = F₁ = 1`. Each iteration computes the next value `a + b`, then shifts the window: the old `b` becomes the new `a`, and the sum becomes the new `b`. After `n` shifts, `a` holds `Fₙ`. Only two variables are ever live, so the space is `O(1)`. **Why it is correct.** It computes the recurrence literally, in order, so every value is the true Fibonacci number. There's no cleverness to get wrong beyond the initial two values and the loop count. **Why it does not scale.** The work is one addition per Fibonacci number, so reaching `Fₙ` costs `Θ(n)` operations. That's perfectly fine for `n ≤ 10⁶`. But the constraint allows `n` up to `10¹⁸`; doing `10¹⁸` additions is hopeless no matter how fast each one is. The cost is tied to the **value** of `n`, not its number of digits. **The leap the optimal makes.** Notice the loop applies the *same* transformation every step — '(a, b) → (b, a+b)'. Applying one fixed transformation `n` times is exactly what raising a matrix to the `n`th power does, and powers can be taken in `O(log n)` by repeated squaring. That observation is the whole speedup. Time complexity: O(n). Space complexity: O(1).

Math & Number Theory · 26 of 36 · 12 min

Compute the nth Fibonacci number Fₙ, where F₀ = 0, F₁ = 1, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2.

n can be as large as 10¹⁸, so an O(n) loop is far too slow. Return Fₙ modulo a given modulus p (Fibonacci numbers grow exponentially, so for large n the answer is always requested mod p).

In plain English

Fibonacci is a linear recurrence: the next number is a fixed linear combination of the previous two. That means the pair (Fₙ, Fₙ₋₁) transforms to (Fₙ₊₁, Fₙ) by multiplying with one fixed 2×2 matrix. Advancing the sequence n steps is the same matrix applied n times — its nth power. Powers can be computed in O(log n) by repeated squaring, so a problem that looks O(n) becomes O(log n). The matrix's nth power literally contains Fₙ in its entries.

Examples

Example 1

Input: n = 10, p = 1000000007
Output: 55
Note: F₁₀ = 55. M¹⁰ = [[89, 55], [55, 34]]; the top-right entry is F₁₀ = 55.

Example 2

Input: n = 1, p = 1000000007
Output: 1
Note: M¹ = [[1,1],[1,0]], so (M¹)[0][1] = 1 = F₁.

Example 3

Input: n = 0, p = 1000000007
Output: 0
Note: M⁰ = identity = [[1,0],[0,1]], so [0][1] = 0 = F₀.

Constraints

0 ≤ n ≤ 10¹⁸ (use 64-bit for n; O(log n) ≈ 60 matrix multiplies)
F₀ = 0, F₁ = 1
Answers are taken mod p with 1 ≤ p ≤ 10⁹ + 7; reduce after every multiply
Entry products of two sub-p values reach ~10¹⁸ → use long in Java

Clarifying questions4First question: How large can n be?Explore questions

Q1.How large can n be?
Up to ~10¹⁸. That rules out the O(n) loop and is exactly why we use the O(log n) matrix power.
Q2.Do you want Fₙ exactly or modulo something?
Fibonacci grows like φⁿ, so for large n it's always mod p. I reduce every matrix entry mod p after each multiplication.
Q3.Which indexing convention — F₀ = 0 or F₁ = 1 first?
F₀ = 0, F₁ = 1. With M = [[1,1],[1,0]], M^n has Fₙ at [0][1]; I'll sanity-check M¹ gives F₁ = 1 and M² gives F₂ = 1.
Q4.Is this a one-off term, or do you need the whole sequence?
One term Fₙ. If the whole sequence up to n were needed and n were modest, a single O(n) pass would beat the matrix method.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

To get the nth Fibonacci number in O(log n) instead of O(n), write the recurrence as a matrix. The step [Fₙ₊₁, Fₙ] = [[1,1],[1,0]] · [Fₙ, Fₙ₋₁] means applying that 2×2 matrix once advances Fibonacci by one. So applying it n times — i.e. raising [[1,1],[1,0]] to the nth power — jumps straight to Fₙ. Compute the matrix power by fast exponentiation (square-and-multiply): M^n needs only O(log n) matrix multiplies, each O(1) for a fixed 2×2. Read Fₙ off the top-right entry of M^n.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can re-express a linear recurrence as repeated multiplication by a fixed matrix, and whether you know fast exponentiation turns 'apply n times' into O(log n) matrix multiplications.

Where candidates slip

Multiplying the matrix n times (still O(n)), getting the index convention wrong so Fₙ comes out shifted by one, or forgetting to reduce matrix entries mod p (overflow / wrong residue).

How to stand out

Derive the transition matrix from the recurrence, prove M^n holds [[F(n+1),F(n)],[F(n),F(n-1)]] by induction, and note the method generalises to any constant-coefficient linear recurrence via its companion matrix.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative DP (Baseline)	`O(n)`	`O(1)`	Mention first — it's the obvious O(n) solution and is the right answer for small n. It anchors the O(n) cost the matrix method beats.	Read
2	Matrix Fast Exponentiation (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want for huge n. Phrase it as 'encode the recurrence as M = [[1,1],[1,0]] and raise it to the nth power by squaring'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Recurrence to matrix power to fast exponentiation

How to read it:The recurrence becomes one matrix multiply per step; n steps is M^n; M^n is computed by squaring in O(log n).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Iterative DP (Baseline)

TimeO(n)SpaceO(1)

Mention first — it's the obvious O(n) solution and is the right answer for small n. It anchors the O(n) cost the matrix method beats.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ translates directly into a loop. What do you need to remember between iterations?

2Hint 2Explore hint

Keep just the last two values, a = Fₙ₋₂ and b = Fₙ₋₁, and slide them forward n times. No array needed — O(1) space.

3Hint 3Explore hint

This is O(n). Fine for n up to ~10⁶, but for n = 10¹⁸ it would take longer than the age of the universe. What lets us skip ahead?

A · Core idea

Translate the recurrence straight into a loop. Hold the previous two Fibonacci numbers in two variables and roll them forward.

How it works. Start with a = F₀ = 0 and b = F₁ = 1. Each iteration computes the next value a + b, then shifts the window: the old b becomes the new a, and the sum becomes the new b. After n shifts, a holds Fₙ. Only two variables are ever live, so the space is O(1).

Why it is correct. It computes the recurrence literally, in order, so every value is the true Fibonacci number. There's no cleverness to get wrong beyond the initial two values and the loop count.

Why it does not scale. The work is one addition per Fibonacci number, so reaching Fₙ costs Θ(n) operations. That's perfectly fine for n ≤ 10⁶. But the constraint allows n up to 10¹⁸; doing 10¹⁸ additions is hopeless no matter how fast each one is. The cost is tied to the value of n, not its number of digits.

The leap the optimal makes. Notice the loop applies the same transformation every step — '(a, b) → (b, a+b)'. Applying one fixed transformation n times is exactly what raising a matrix to the nth power does, and powers can be taken in O(log n) by repeated squaring. That observation is the whole speedup.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10

init

a=0 (F0), b=1 (F1)

Statea=0, b=1

Final result55

C · Code with teaching comments

Reference implementation previewpublic long fib(long n, long p) { if (n == 0) return 0; long a = 0, b = 1 % p; for (long i = 2; i <= n; i++) { long next = (a + b) % p;Explore the full code

solution.javaJava

Iterative DP (Baseline) — reference

3 teaching notes

1
public long fib(long n, long p) {
2
    if (n == 0) return 0;
3
    // Seed F0 and F1; the 1 % p keeps it correct when p = 1.
4
    long a = 0, b = 1 % p;
5
    for (long i = 2; i <= n; i++) {
6
        // The recurrence step, reduced mod p so values stay bounded.
7
        long next = (a + b) % p;
8
        a = b;
9
        b = next;
10
    }
11
    // After the loop b holds Fₙ.
12
    return b;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The iterative DP is correct and is the right tool whenever n is small. Its only flaw is that its cost grows with the value of n, not its bit-length. The matrix method keeps the same transformation but applies it via exponentiation, so cost grows with log n instead.

ComplexityO(n) time, O(1) space — One addition per step, n steps, so O(n) time. Only two running values are kept, so O(1) space. The wall is n itself: when n is 10¹⁸, n iterations is infeasible regardless of how cheap each step is.

E · Edge cases and pitfalls3Running it for n = 10¹⁸ — O(n) is infeasible.Explore edge cases

Pitfalls

Running it for n = 10¹⁸ — O(n) is infeasible.
Mishandling n = 0 or n = 1 base cases.
Forgetting the mod and letting values grow unbounded (slow in Python, overflow in Java).

03.2

Approach 2 of 2 · Optimal

Matrix Fast Exponentiation (Optimal)

TimeO(log n)SpaceO(1)

The answer they want for huge n. Phrase it as 'encode the recurrence as M = [[1,1],[1,0]] and raise it to the nth power by squaring'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the step as a matrix: [Fₙ₊₁, Fₙ]ᵀ = M · [Fₙ, Fₙ₋₁]ᵀ. What 2×2 matrix M makes that true?

2Hint 2Explore hint

M = [[1,1],[1,0]]. Applying it once advances the pair by one Fibonacci step, so applying it n times is M^n. What does M^n do to the starting vector [F₁, F₀] = [1, 0]?

3Hint 3Explore hint

Compute M^n by fast exponentiation: square M repeatedly, multiply the accumulator by the current square whenever that bit of n is 1. O(log n) matrix multiplies, each O(1) for a fixed 2×2.

A · Core idea

Re-express the recurrence as a single matrix transformation, then raise that matrix to the nth power with repeated squaring.

Building the transition matrix. The recurrence Fₙ₊₁ = Fₙ + Fₙ₋₁ and the trivial Fₙ = Fₙ together say:

[Fₙ₊₁, Fₙ]ᵀ = [[1,1],[1,0]] · [Fₙ, Fₙ₋₁]ᵀ.

Call that matrix M = [[1,1],[1,0]]. Multiplying by M once advances the state pair by exactly one Fibonacci step. So advancing n steps from [F₁, F₀] = [1, 0] is multiplying by M a total of n times — i.e. computing M^n.

Why M^n contains Fₙ. A short induction shows M^n = [[Fₙ₊₁, Fₙ], [Fₙ, Fₙ₋₁]]. Base case M¹ = [[1,1],[1,0]] = [[F₂,F₁],[F₁,F₀]] ✓. Inductive step: M^(n+1) = M^n · M, and multiplying out [[Fₙ₊₁,Fₙ],[Fₙ,Fₙ₋₁]] · [[1,1],[1,0]] gives [[Fₙ₊₁+Fₙ, Fₙ₊₁],[Fₙ+Fₙ₋₁, Fₙ]] = [[Fₙ₊₂,Fₙ₊₁],[Fₙ₊₁,Fₙ]] ✓. So Fₙ sits at position [0][1] (and [1][0]) of M^n.

Why fast exponentiation, not n multiplies. Computing M^n by multiplying M into an accumulator n times is still O(n) — no gain. Instead use square-and-multiply: write n in binary; keep a running square base = M, M², M⁴, … and an accumulator result that starts as the identity. For each bit of n from least significant, if the bit is 1 multiply result *= base, then square base. Because n has only ⌊log₂ n⌋ + 1 bits, this does O(log n) matrix multiplications. Each multiply is a constant amount of work for a fixed 2×2.

Why start at the identity. In scalar exponentiation the accumulator starts at 1; the matrix analogue is the identity matrix [[1,0],[0,1]], which leaves any matrix unchanged when multiplied. It also handles n = 0 for free: M⁰ = I, and I[0][1] = 0 = F₀.

Why reduce mod p and use long. Each entry of a product is a sum of two products of entries, each entry below p ≈ 10⁹. A single product reaches ~10¹⁸, which fits in a signed 64-bit long — but you must take mod p after each entry multiplication so it never compounds. Python integers are unbounded, so the mod there keeps numbers small and matches the math.

Why it generalises. Any linear recurrence with constant coefficients has a companion transition matrix (size k×k for a k-term recurrence). The same M^n idea computes its nth term in O(k³ log n). Counting length-n walks in a graph is the same trick on the adjacency matrix.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, p = 1000000007

Array state

M^1

base = M

[0]

F1 ↓

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result55

C · Code with teaching comments

solution.javaJava

Matrix Fast Exponentiation (Optimal) — optimal

5 teaching notes

1
public long fib(long n, long p) {
2
    long[][] result = {{1, 0}, {0, 1}}; // identity
3
    long[][] base = {{1, 1}, {1, 0}};   // M
4
    while (n > 0) {
5
        // When the current bit of n is set, fold the current square into the result —
6
        // the 'multiply' of square-and-multiply.
7
        if ((n & 1) == 1) result = multiply(result, base, p);
8
        // Square the base each step: M, M², M⁴, … — the 'square' half.
9
        base = multiply(base, base, p);
10
        n >>= 1;
11
    }
12
    return result[0][1]; // F(n)
13
}
14
 
15
private long[][] multiply(long[][] A, long[][] B, long p) {
16
    long[][] C = new long[2][2];
17
    for (int i = 0; i < 2; i++) {
18
        for (int j = 0; j < 2; j++) {
19
            long sum = 0;
20
            for (int k = 0; k < 2; k++) {
21
                sum = (sum + A[i][k] * B[k][j]) % p; // mod after each multiply
22
            }
23
            C[i][j] = sum;
24
        }
25
    }
26
    return C;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

The unifying idea: 'apply the same linear step n times' equals 'a fixed matrix to the nth power', and powers are cheap by squaring. Fibonacci is the smallest non-trivial instance — a 2×2 matrix — but the construction is identical for any constant-coefficient linear recurrence or for counting walks via an adjacency matrix. The reframe from O(n) to O(log n) is purely 'powers can be squared'.

ComplexityO(log n) time, O(1) space — Fast exponentiation does at most 2·log₂(n) matrix multiplications. Each multiply of two 2×2 matrices is a constant 8 multiplications and 4 additions. So total time is O(log n) with O(1) space (a handful of 2×2 matrices).

E · Edge cases and pitfalls9n = 0 — Loop never executes; result stays identity; [0][1] = 0 = F₀.Explore edge cases

Edge cases handled

n = 0Loop never executes; result stays identity; [0][1] = 0 = F₀.
n = 1One set bit: result = M; [0][1] = 1 = F₁.
p = 1Every entry reduces to 0 mod 1; returns 0, the only residue.
n = 10¹⁸About 60 squarings — completes instantly, unlike the O(n) loop.

Pitfalls

Multiplying M into the accumulator n times instead of squaring — still O(n).
Starting the accumulator at M instead of the identity — off by one power and breaks n = 0.
Reading Fₙ from the wrong entry — it's [0][1] (and [1][0]), not [0][0].
Forgetting mod after each entry multiply — overflow in Java or slow big ints in Python.
Using int for entries in Java — products reach ~10¹⁸; must be long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long fib(long n, long p) { long[][] result = {{1, 0}, {0, 1}}; // identity long[][] base = {{1, 1}, {1, 0}}; // M while (n > 0) { if ((n & 1) == 1) result = multiply(result, base, p);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Linear instead of logarithmic exponentiation

Multiplying M into the result n times is O(n) — no better than the loop. Fast exponentiation squares the base and multiplies on set bits, giving O(log n).

Explore the code comparison

Don't write this

long[][] result = base;
for (long i = 1; i < n; i++) {
    result = multiply(result, base, p); // O(n) multiplies
}

Write this instead

long[][] result = identity();
while (n > 0) {
    if ((n & 1) == 1) result = multiply(result, base, p);
    base = multiply(base, base, p); // square each step
    n >>= 1;
}

Reading the wrong entry of M^n

M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]. Fₙ is the off-diagonal [0][1], not the top-left [0][0] (which is Fₙ₊₁). Reading [0][0] returns the next Fibonacci number.

Explore the code comparison

Don't write this

return result[0][0]   # that's F(n+1), off by one

Write this instead

return result[0][1]   # F(n)

No mod after entry multiplication

An entry product of two values near 10⁹ is ~10¹⁸; summing two of them without reducing overflows a signed 64-bit long and yields garbage.

Explore the code comparison

Don't write this

C[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j]; // can overflow long

Write this instead

C[i][j] = (A[i][0] * B[0][j] % p + A[i][1] * B[1][j] % p) % p;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Encode a linear recurrence as a matrix, then fast-exponentiate the matrix

Code pattern to memorize

M = [[1, 1], [1, 0]]
M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
so F(n) = (M^n)[0][1]
fast power: M^n via square-and-multiply in O(log n) 2x2 multiplies

Rules to remember

1The transition matrix [[1,1],[1,0]] raised to n has Fₙ in both off-diagonal entries; read Fₙ from (M^n)[0][1].
2Use fast exponentiation (square the matrix, multiply when the bit is set) — n multiplications would be O(n) and defeat the purpose.
3Start the result as the identity matrix [[1,0],[0,1]], the matrix equivalent of 1 in scalar power.
4Reduce every matrix entry mod p after each multiply when working under a modulus, and use long in Java — entry products of two sub-p values reach ~10¹⁸.
5Pin down F₀ = 0, F₁ = 1 (so M¹ = M gives F₁ = 1). An off-by-one in the indexing convention is the usual bug; verify against M² = [[2,1],[1,1]] → F₂ = 1.

Use this pattern when

You need `Fₙ` (or any linear-recurrence term) for **astronomically large** n — `10¹⁸` — where O(n) is impossible
The recurrence is **linear with constant coefficients**: `aₙ = c₁aₙ₋₁ + … + c_k aₙ₋ₖ`
You want `Fₙ mod p` for huge n in counting / combinatorics problems
Counting walks of length n in a graph (the adjacency matrix to the nth power)

Choose another pattern when

n is small (≤ 10⁶) → the O(n) iterative DP is simpler and fast enough
The recurrence is **non-linear** (e.g. `aₙ = aₙ₋₁²`) → no constant matrix encodes it
You need the **whole sequence** F₀..Fₙ, not one term → iterate once in O(n)
Coefficients change with n → not a fixed transition matrix

Interview takeaway

Any linear recurrence with constant coefficients is 'multiply the state vector by a fixed transition matrix once per step'. n steps = that matrix to the nth power, and fast exponentiation computes a power in O(log n) multiplies. For Fibonacci the matrix is the 2×2 [[1,1],[1,0]], and Fₙ falls out of its nth power. The trick generalises: build the companion matrix of any k-term linear recurrence and you get O(k³ log n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMatrix exponentiation of a linear recurrence. Reach for it whenever you need a single far-out term of a constant-coefficient linear recurrence (or a count of length-n walks) and O(n) is too slow. Encode one step as a fixed matrix, raise it to the nth power by squaring — O(log n). Fibonacci's 2×2 is the canonical instance.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Modular Exponentiation
Scalar square-and-multiply — the same engine, applied to numbers instead of matrices.
Pow(x, n)
Fast exponentiation on a real base; identical squaring structure.
Tribonacci / k-term Recurrence
Coming soon
Build the k×k companion matrix and raise it to the nth power in O(k³ log n).
Count Walks of Length n in a Graph
Coming soon
The (i, j) entry of A^n is the number of length-n walks from i to j.

Same pattern

←

Lucas' Theorem

Continue · Next problem

nCr mod p

mediumMath GeometrySometimes asked

Matrix Exponentiation (Fibonacci)

Math & Number Theory · 26 of 36 · 12 min

Compute the nth Fibonacci number Fₙ, where F₀ = 0, F₁ = 1, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2.

In plain English

Examples

Example 1

Input: n = 10, p = 1000000007
Output: 55
Note: F₁₀ = 55. M¹⁰ = [[89, 55], [55, 34]]; the top-right entry is F₁₀ = 55.

Example 2

Input: n = 1, p = 1000000007
Output: 1
Note: M¹ = [[1,1],[1,0]], so (M¹)[0][1] = 1 = F₁.

Example 3

Input: n = 0, p = 1000000007
Output: 0
Note: M⁰ = identity = [[1,0],[0,1]], so [0][1] = 0 = F₀.

Constraints

0 ≤ n ≤ 10¹⁸ (use 64-bit for n; O(log n) ≈ 60 matrix multiplies)
F₀ = 0, F₁ = 1
Answers are taken mod p with 1 ≤ p ≤ 10⁹ + 7; reduce after every multiply
Entry products of two sub-p values reach ~10¹⁸ → use long in Java

Clarifying questions4First question: How large can n be?Explore questions

Q1.How large can n be?
Up to ~10¹⁸. That rules out the O(n) loop and is exactly why we use the O(log n) matrix power.
Q2.Do you want Fₙ exactly or modulo something?
Fibonacci grows like φⁿ, so for large n it's always mod p. I reduce every matrix entry mod p after each multiplication.
Q3.Which indexing convention — F₀ = 0 or F₁ = 1 first?
F₀ = 0, F₁ = 1. With M = [[1,1],[1,0]], M^n has Fₙ at [0][1]; I'll sanity-check M¹ gives F₁ = 1 and M² gives F₂ = 1.
Q4.Is this a one-off term, or do you need the whole sequence?
One term Fₙ. If the whole sequence up to n were needed and n were modest, a single O(n) pass would beat the matrix method.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can re-express a linear recurrence as repeated multiplication by a fixed matrix, and whether you know fast exponentiation turns 'apply n times' into O(log n) matrix multiplications.

Where candidates slip

Multiplying the matrix n times (still O(n)), getting the index convention wrong so Fₙ comes out shifted by one, or forgetting to reduce matrix entries mod p (overflow / wrong residue).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative DP (Baseline)	`O(n)`	`O(1)`	Mention first — it's the obvious O(n) solution and is the right answer for small n. It anchors the O(n) cost the matrix method beats.	Read
2	Matrix Fast Exponentiation (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want for huge n. Phrase it as 'encode the recurrence as M = [[1,1],[1,0]] and raise it to the nth power by squaring'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Recurrence to matrix power to fast exponentiation

How to read it:The recurrence becomes one matrix multiply per step; n steps is M^n; M^n is computed by squaring in O(log n).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Iterative DP (Baseline)

TimeO(n)SpaceO(1)

Mention first — it's the obvious O(n) solution and is the right answer for small n. It anchors the O(n) cost the matrix method beats.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ translates directly into a loop. What do you need to remember between iterations?

2Hint 2Explore hint

Keep just the last two values, a = Fₙ₋₂ and b = Fₙ₋₁, and slide them forward n times. No array needed — O(1) space.

3Hint 3Explore hint

This is O(n). Fine for n up to ~10⁶, but for n = 10¹⁸ it would take longer than the age of the universe. What lets us skip ahead?

A · Core idea

Translate the recurrence straight into a loop. Hold the previous two Fibonacci numbers in two variables and roll them forward.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10

init

a=0 (F0), b=1 (F1)

Statea=0, b=1

Final result55

C · Code with teaching comments

Reference implementation previewpublic long fib(long n, long p) { if (n == 0) return 0; long a = 0, b = 1 % p; for (long i = 2; i <= n; i++) { long next = (a + b) % p;Explore the full code

solution.javaJava

Iterative DP (Baseline) — reference

3 teaching notes

1
public long fib(long n, long p) {
2
    if (n == 0) return 0;
3
    // Seed F0 and F1; the 1 % p keeps it correct when p = 1.
4
    long a = 0, b = 1 % p;
5
    for (long i = 2; i <= n; i++) {
6
        // The recurrence step, reduced mod p so values stay bounded.
7
        long next = (a + b) % p;
8
        a = b;
9
        b = next;
10
    }
11
    // After the loop b holds Fₙ.
12
    return b;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Running it for n = 10¹⁸ — O(n) is infeasible.Explore edge cases

Pitfalls

Running it for n = 10¹⁸ — O(n) is infeasible.
Mishandling n = 0 or n = 1 base cases.
Forgetting the mod and letting values grow unbounded (slow in Python, overflow in Java).

03.2

Approach 2 of 2 · Optimal

Matrix Fast Exponentiation (Optimal)

TimeO(log n)SpaceO(1)

The answer they want for huge n. Phrase it as 'encode the recurrence as M = [[1,1],[1,0]] and raise it to the nth power by squaring'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the step as a matrix: [Fₙ₊₁, Fₙ]ᵀ = M · [Fₙ, Fₙ₋₁]ᵀ. What 2×2 matrix M makes that true?

2Hint 2Explore hint

M = [[1,1],[1,0]]. Applying it once advances the pair by one Fibonacci step, so applying it n times is M^n. What does M^n do to the starting vector [F₁, F₀] = [1, 0]?

3Hint 3Explore hint

Compute M^n by fast exponentiation: square M repeatedly, multiply the accumulator by the current square whenever that bit of n is 1. O(log n) matrix multiplies, each O(1) for a fixed 2×2.

A · Core idea

Re-express the recurrence as a single matrix transformation, then raise that matrix to the nth power with repeated squaring.

Building the transition matrix. The recurrence Fₙ₊₁ = Fₙ + Fₙ₋₁ and the trivial Fₙ = Fₙ together say:

[Fₙ₊₁, Fₙ]ᵀ = [[1,1],[1,0]] · [Fₙ, Fₙ₋₁]ᵀ.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, p = 1000000007

Array state

M^1

base = M

[0]

F1 ↓

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result55

C · Code with teaching comments

solution.javaJava

Matrix Fast Exponentiation (Optimal) — optimal

5 teaching notes

1
public long fib(long n, long p) {
2
    long[][] result = {{1, 0}, {0, 1}}; // identity
3
    long[][] base = {{1, 1}, {1, 0}};   // M
4
    while (n > 0) {
5
        // When the current bit of n is set, fold the current square into the result —
6
        // the 'multiply' of square-and-multiply.
7
        if ((n & 1) == 1) result = multiply(result, base, p);
8
        // Square the base each step: M, M², M⁴, … — the 'square' half.
9
        base = multiply(base, base, p);
10
        n >>= 1;
11
    }
12
    return result[0][1]; // F(n)
13
}
14
 
15
private long[][] multiply(long[][] A, long[][] B, long p) {
16
    long[][] C = new long[2][2];
17
    for (int i = 0; i < 2; i++) {
18
        for (int j = 0; j < 2; j++) {
19
            long sum = 0;
20
            for (int k = 0; k < 2; k++) {
21
                sum = (sum + A[i][k] * B[k][j]) % p; // mod after each multiply
22
            }
23
            C[i][j] = sum;
24
        }
25
    }
26
    return C;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls9n = 0 — Loop never executes; result stays identity; [0][1] = 0 = F₀.Explore edge cases

Edge cases handled

n = 0Loop never executes; result stays identity; [0][1] = 0 = F₀.
n = 1One set bit: result = M; [0][1] = 1 = F₁.
p = 1Every entry reduces to 0 mod 1; returns 0, the only residue.
n = 10¹⁸About 60 squarings — completes instantly, unlike the O(n) loop.

Pitfalls

Multiplying M into the accumulator n times instead of squaring — still O(n).
Starting the accumulator at M instead of the identity — off by one power and breaks n = 0.
Reading Fₙ from the wrong entry — it's [0][1] (and [1][0]), not [0][0].
Forgetting mod after each entry multiply — overflow in Java or slow big ints in Python.
Using int for entries in Java — products reach ~10¹⁸; must be long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Linear instead of logarithmic exponentiation

Multiplying M into the result n times is O(n) — no better than the loop. Fast exponentiation squares the base and multiplies on set bits, giving O(log n).

Explore the code comparison

Don't write this

long[][] result = base;
for (long i = 1; i < n; i++) {
    result = multiply(result, base, p); // O(n) multiplies
}

Write this instead

long[][] result = identity();
while (n > 0) {
    if ((n & 1) == 1) result = multiply(result, base, p);
    base = multiply(base, base, p); // square each step
    n >>= 1;
}

Reading the wrong entry of M^n

M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]. Fₙ is the off-diagonal [0][1], not the top-left [0][0] (which is Fₙ₊₁). Reading [0][0] returns the next Fibonacci number.

Explore the code comparison

Don't write this

return result[0][0]   # that's F(n+1), off by one

Write this instead

return result[0][1]   # F(n)

No mod after entry multiplication

An entry product of two values near 10⁹ is ~10¹⁸; summing two of them without reducing overflows a signed 64-bit long and yields garbage.

Explore the code comparison

Don't write this

C[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j]; // can overflow long

Write this instead

C[i][j] = (A[i][0] * B[0][j] % p + A[i][1] * B[1][j] % p) % p;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Encode a linear recurrence as a matrix, then fast-exponentiate the matrix

Code pattern to memorize

M = [[1, 1], [1, 0]]
M^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
so F(n) = (M^n)[0][1]
fast power: M^n via square-and-multiply in O(log n) 2x2 multiplies

Rules to remember

1The transition matrix [[1,1],[1,0]] raised to n has Fₙ in both off-diagonal entries; read Fₙ from (M^n)[0][1].
2Use fast exponentiation (square the matrix, multiply when the bit is set) — n multiplications would be O(n) and defeat the purpose.
3Start the result as the identity matrix [[1,0],[0,1]], the matrix equivalent of 1 in scalar power.
4Reduce every matrix entry mod p after each multiply when working under a modulus, and use long in Java — entry products of two sub-p values reach ~10¹⁸.
5Pin down F₀ = 0, F₁ = 1 (so M¹ = M gives F₁ = 1). An off-by-one in the indexing convention is the usual bug; verify against M² = [[2,1],[1,1]] → F₂ = 1.

Use this pattern when

You need `Fₙ` (or any linear-recurrence term) for **astronomically large** n — `10¹⁸` — where O(n) is impossible
The recurrence is **linear with constant coefficients**: `aₙ = c₁aₙ₋₁ + … + c_k aₙ₋ₖ`
You want `Fₙ mod p` for huge n in counting / combinatorics problems
Counting walks of length n in a graph (the adjacency matrix to the nth power)

Choose another pattern when

n is small (≤ 10⁶) → the O(n) iterative DP is simpler and fast enough
The recurrence is **non-linear** (e.g. `aₙ = aₙ₋₁²`) → no constant matrix encodes it
You need the **whole sequence** F₀..Fₙ, not one term → iterate once in O(n)
Coefficients change with n → not a fixed transition matrix

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Modular Exponentiation
Scalar square-and-multiply — the same engine, applied to numbers instead of matrices.
Pow(x, n)
Fast exponentiation on a real base; identical squaring structure.
Tribonacci / k-term Recurrence
Coming soon
Build the k×k companion matrix and raise it to the nth power in O(k³ log n).
Count Walks of Length n in a Graph
Coming soon
The (i, j) entry of A^n is the number of length-n walks from i to j.

Same pattern

←

Lucas' Theorem

Continue · Next problem

nCr mod p