Loading…

mediumMath GeometryAsked very often

Nth Fibonacci Number

Q: How do you solve Nth Fibonacci Number using the Iterative Bottom-Up, Two Variables (Baseline) approach?

When to use it: The clean default — mention naive recursion is exponential, then jump straight to this O(1)-space loop. Build the sequence from the bottom, carrying only the two most recent values. Seed `a = F(0) = 0` and `b = F(1) = 1`, then repeat `(a, b) = (b, a + b)` exactly `n` times; `a` then holds `F(n)`. **Why naive recursion is a trap.** Writing `fib(n) = fib(n-1) + fib(n-2)` looks like the definition, but it rebuilds the same subtrees over and over — `fib(n-2)` is computed twice, `fib(n-3)` three times, and so on. The call count grows like `φⁿ` (golden-ratio base), so `fib(50)` already takes seconds. Mention it only to dismiss it. **Why two variables suffice.** The recurrence reaches back exactly two terms. Once you've produced `F(i)`, you never need anything older than `F(i-1)` again. So a full `dp[]` array is wasted memory — two rolling scalars capture all the state, dropping space from O(n) to O(1). This 'roll the window' move generalizes to any fixed-depth linear recurrence. **Why the loop runs n times and a is the answer.** Start `(a, b)` as `(F(0), F(1))`. Each roll advances the window by one index: after one roll `a = F(1)`, after two `a = F(2)`, …, after `n` rolls `a = F(n)`. Returning `a` (not `b`) is the off-by-one most people get wrong — trace the first couple of iterations to be sure. **Why overflow still bites.** Fibonacci grows exponentially (~`φⁿ`), so it blows past a 64-bit `long` at `F(93)`. The loop is correct, but the *type* must widen to `BigInteger` for large `n`. In Python this is automatic; in Java, say it out loud. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Nth Fibonacci Number using the Fast Doubling (Optimal, O(log n)) approach?

When to use it: When n is astronomically large or the interviewer pushes past O(n). Cite the doubling identities. Compute `F(n)` by halving the index instead of decrementing it — the same trick that turns exponentiation into O(log n). Each level computes `(F(k), F(k+1))` from `(F(k/2), F(k/2 + 1))` using two closed-form identities. **The identities and why they work.** From the matrix form of Fibonacci you can derive: - `F(2k) = F(k) · (2·F(k+1) − F(k))` - `F(2k+1) = F(k)² + F(k+1)²` Given the pair at index `k`, these produce the pair at index `2k` in a constant number of multiplications. Because doubling the index each step covers `n` in `log₂ n` doublings, the whole computation is logarithmic. **Why we track a *pair*, not a single value.** Both identities need `F(k)` *and* `F(k+1)` to step to the next level. So the recursion returns the tuple `(F(k), F(k+1))`; at each return we compute the doubled pair and then, if the current bit of `n` is `1`, shift by one more (the `(F(2k+1), F(2k) + F(2k+1))` adjustment) to land on the correct index. Read `n` bit by bit from the most significant end. **Why it beats matrix exponentiation in practice.** Matrix exponentiation raises `[[1,1],[1,0]]` to the `n`-th power, also O(log n), but each step does eight scalar multiplies for the 2×2 product. Fast doubling does just a few multiplies per level for the *same* asymptotic bound, so it wins on constant factors and is less error-prone to code. Mention both; prefer doubling. **Why O(log n) is a refinement, not free.** For large `n` the numbers themselves are huge (BigInteger), so each multiply isn't truly O(1). The honest claim is O(log n) *arithmetic operations*; the bit-complexity is higher. Still vastly better than O(n) additions on giant numbers. Time complexity: O(log n). Space complexity: O(log n) recursion stack.

Math & Number Theory · 28 of 36 · 9 min

Return the n-th Fibonacci number, where F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2) for n ≥ 2.

Discuss how your approach scales as n grows and what happens to the return type.

In plain English

Each term is the sum of the two before it. You only ever need the previous two values to produce the next, so the whole sequence can be walked with constant memory — and a doubling identity skips most of the work entirely.

Examples

Example 1

Input: n = 0
Output: 0
Note: Base case F(0) = 0.

Example 2

Input: n = 10
Output: 55
Note: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 — F(10) = 55.

Example 3

Input: n = 93
Output: 12200160415121876738
Note: F(93) exceeds Long.MAX_VALUE (~9.2 × 10¹⁸), so a long-based answer overflows — BigInteger required.

Constraints

0 ≤ n ≤ 92 if the answer must fit in a signed 64-bit integer
0 ≤ n ≤ 10⁶ or beyond with BigInteger / arbitrary precision
Indexing: F(0) = 0, F(1) = 1

Clarifying questions4First question: What indexing — does F(0) = 0 or F(1) = 1 start the sequence?Explore questions

Q1.What indexing — does F(0) = 0 or F(1) = 1 start the sequence?
I'll use F(0) = 0, F(1) = 1. The convention matters because an off-by-one shifts every value; I'd confirm yours.
Q2.How large can n be?
If n stays under ~92, a long holds F(n). Beyond that I switch to BigInteger, or use fast doubling if n is huge.
Q3.Do you want F(n) exactly, or modulo something?
If it's F(n) mod m for enormous n, I'd run fast doubling under the modulus rather than computing the full number.
Q4.Is a single value needed, or the whole prefix?
If you need every F(0..n) I'd keep the array; for a single value the two-variable roll is enough.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Iterate bottom-up keeping only the last two values for O(n) time and O(1) space. When n is huge, use fast doubling (or matrix exponentiation) to compute F(n) in O(log n) via the identities F(2k) = F(k)·(2F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)².

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize naive recursion is exponential, reach for the O(1)-space iterative form, and — for the medium bar — know that an O(log n) method exists and why.

Where candidates slip

Submitting exponential recursion, getting the F(0)/F(1) base case off by one, or overflowing a long around F(93) without noticing.

How to stand out

Walk the full ladder: exponential recursion → memoized O(n) → iterative O(n) O(1) space → fast doubling O(log n). State the overflow point and offer BigInteger.

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 Bottom-Up, Two Variables (Baseline)	`O(n)`	`O(1)`	The clean default — mention naive recursion is exponential, then jump straight to this O(1)-space loop.	Read
2	Fast Doubling (Optimal, O(log n))Optimal	`O(log n)`	`O(log n) recursion stack`	When n is astronomically large or the interviewer pushes past O(n). Cite the doubling identities.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompute F(n)How big is n?tiny / interviewhugeExplore the full tree

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 Bottom-Up, Two Variables (Baseline)

TimeO(n)SpaceO(1)

The clean default — mention naive recursion is exponential, then jump straight to this O(1)-space loop.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Naive recursion recomputes fib(n-2) over and over. What's the minimum history you actually need to produce the next term?

2Hint 2Explore hint

Just the previous two values. Carry a = F(i-1), b = F(i), and roll them forward n times.

3Hint 3Explore hint

Start a, b = 0, 1 and repeat a, b = b, a + b. After n rolls, a holds F(n).

A · Core idea

Build the sequence from the bottom, carrying only the two most recent values. Seed a = F(0) = 0 and b = F(1) = 1, then repeat (a, b) = (b, a + b) exactly n times; a then holds F(n).

Why naive recursion is a trap. Writing fib(n) = fib(n-1) + fib(n-2) looks like the definition, but it rebuilds the same subtrees over and over — fib(n-2) is computed twice, fib(n-3) three times, and so on. The call count grows like φⁿ (golden-ratio base), so fib(50) already takes seconds. Mention it only to dismiss it.

Why two variables suffice. The recurrence reaches back exactly two terms. Once you've produced F(i), you never need anything older than F(i-1) again. So a full dp[] array is wasted memory — two rolling scalars capture all the state, dropping space from O(n) to O(1). This 'roll the window' move generalizes to any fixed-depth linear recurrence.

Why the loop runs n times and a is the answer. Start (a, b) as (F(0), F(1)). Each roll advances the window by one index: after one roll a = F(1), after two a = F(2), …, after n rolls a = F(n). Returning a (not b) is the off-by-one most people get wrong — trace the first couple of iterations to be sure.

Why overflow still bites. Fibonacci grows exponentially (~`φⁿ), so it blows past a 64-bit longatF(93). The loop is correct, but the *type* must widen to BigIntegerfor largen`. In Python this is automatic; in Java, say it out loud.

B · Visual dry run

Interactive dry run

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

n = 6

Array state

roll 2

(a, b) = (1, 2)

[0]

[1]

a ↓

[2]

b ↓

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result8

C · Code with teaching comments

Reference implementation previewpublic long fib(int n) { if (n < 0) { throw new IllegalArgumentException("n must be non-negative"); } long a = 0, b = 1;Explore the full code

solution.javaJava

Iterative Bottom-Up, Two Variables (Baseline) — reference

4 teaching notes

1
public long fib(int n) {
2
    if (n < 0) {
3
        throw new IllegalArgumentException("n must be non-negative");
4
    }
5
    // Seed with F(0) and F(1). a will end up holding F(n).
6
    long a = 0, b = 1;
7
    // Exactly n rolls advance a from F(0) to F(n).
8
    for (int i = 0; i < n; i++) {
9
        long next = a + b;   // overflows a long past n = 92
10
        a = b;
11
        b = next;
12
    }
13
    // Return a, NOT b — the classic off-by-one is returning b (which is F(n+1)).
14
    return a;
15
}

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

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

You only need the last two terms, so the natural-looking DP array collapses to two variables and O(1) space. That window-rolling instinct — keep only what the recurrence references — is the reusable idea, not Fibonacci itself.

ComplexityO(n) time, O(1) space — One loop of n iterations, each doing a constant-time addition and reassignment. Only two scalars are stored, so space is O(1) — no DP array needed.

E · Edge cases and pitfalls3Submitting exponential naive recursion.Explore edge cases

Pitfalls

Submitting exponential naive recursion.
Returning b instead of a (off-by-one — b is F(n+1)).
Overflowing a long at F(93) without noticing.

03.2

Approach 2 of 2 · Optimal

Fast Doubling (Optimal, O(log n))

TimeO(log n)SpaceO(log n) recursion stack

When n is astronomically large or the interviewer pushes past O(n). Cite the doubling identities.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The iterative method does n additions. Could you jump from F(k) straight to F(2k), halving the index each step like fast exponentiation?

2Hint 2Explore hint

Yes — there are identities expressing F(2k) and F(2k+1) purely in terms of F(k) and F(k+1).

3Hint 3Explore hint

Recurse on n >> 1 (n / 2), get (F(k), F(k+1)), then combine: F(2k) = F(k)·(2F(k+1) − F(k)), F(2k+1) = F(k)² + F(k+1)². Pick the right pair based on the low bit of n.

A · Core idea

Compute F(n) by halving the index instead of decrementing it — the same trick that turns exponentiation into O(log n). Each level computes (F(k), F(k+1)) from (F(k/2), F(k/2 + 1)) using two closed-form identities.

The identities and why they work. From the matrix form of Fibonacci you can derive:

F(2k) = F(k) · (2·F(k+1) − F(k))
F(2k+1) = F(k)² + F(k+1)²

Given the pair at index k, these produce the pair at index 2k in a constant number of multiplications. Because doubling the index each step covers n in log₂ n doublings, the whole computation is logarithmic.

Why we track a *pair*, not a single value. Both identities need F(k) and F(k+1) to step to the next level. So the recursion returns the tuple (F(k), F(k+1)); at each return we compute the doubled pair and then, if the current bit of n is 1, shift by one more (the (F(2k+1), F(2k) + F(2k+1)) adjustment) to land on the correct index. Read n bit by bit from the most significant end.

Why it beats matrix exponentiation in practice. Matrix exponentiation raises [[1,1],[1,0]] to the n-th power, also O(log n), but each step does eight scalar multiplies for the 2×2 product. Fast doubling does just a few multiplies per level for the same asymptotic bound, so it wins on constant factors and is less error-prone to code. Mention both; prefer doubling.

Why O(log n) is a refinement, not free. For large n the numbers themselves are huge (BigInteger), so each multiply isn't truly O(1). The honest claim is O(log n) arithmetic operations; the bit-complexity is higher. Still vastly better than O(n) additions on giant numbers.

B · Visual dry run

Interactive dry run

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

n = 6 (binary 110)

Interactive diagram

Halving the index each level

n=0

Active call / nodeSupporting contextReturned stateNot active

Fast doubling processes the bits of n, so depth is log₂ n rather than n.

Final result8

C · Code with teaching comments

solution.javaJava

Fast Doubling (Optimal, O(log n)) — optimal

4 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fib(int n) {
4
    return fibPair(n)[0];
5
}
6
 
7
// returns {F(n), F(n+1)}
8
private BigInteger[] fibPair(int n) {
9
    if (n == 0) {
10
        return new BigInteger[]{BigInteger.ZERO, BigInteger.ONE};
11
    }
12
    // Recurse on n/2 — each level halves the index, giving O(log n) depth.
13
    BigInteger[] half = fibPair(n >> 1);
14
    BigInteger fk = half[0], fk1 = half[1];
15
    // F(2k) = F(k) * (2*F(k+1) - F(k))
16
    // F(2k) = F(k)·(2F(k+1) − F(k)); shiftLeft(1) is the ×2.
17
    BigInteger c = fk.multiply(fk1.shiftLeft(1).subtract(fk));
18
    // F(2k+1) = F(k)^2 + F(k+1)^2
19
    // F(2k+1) = F(k)² + F(k+1)².
20
    BigInteger d = fk.multiply(fk).add(fk1.multiply(fk1));
21
    if ((n & 1) == 0) {
22
        return new BigInteger[]{c, d};        // even index
23
    } else {
24
        return new BigInteger[]{d, c.add(d)}; // odd index: shift by one
25
    }
26
}

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

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

Fibonacci satisfies a doubling recurrence, so the same divide-the-exponent strategy behind fast power applies to the index. Recognizing that a linear recurrence has a logarithmic shortcut — via matrix power or these identities — is the medium-level signal.

ComplexityO(log n) time, O(log n) recursion stack space — Each recursive call halves n (processes one bit), so there are O(log n) calls; each does a constant number of multiplications. With fixed-width ints those multiplies are O(1), giving O(log n); with BigInteger the multiplies grow, but the call count is still log n.

E · Edge cases and pitfalls6n = 0 — Base case returns the pair (0, 1); fib returns 0.Explore edge cases

Edge cases handled

n = 0Base case returns the pair (0, 1); fib returns 0.
n = 1Recurses to n=0, doubles+shifts to (1, 1); returns 1.
n = 93Exceeds a long; BigInteger returns the exact 12200160415121876738.

Pitfalls

Mixing up which identity is F(2k) vs F(2k+1).
Forgetting the odd-bit shift, landing one index off.
Claiming flat O(log n) for big n — the BigInteger multiplies themselves grow.

Practice

Try the solution yourself

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

Editable code previewimport java.math.BigInteger; public BigInteger fib(int n) { return fibPair(n)[0]; }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.

Exponential naive recursion

fib(n-1) + fib(n-2) recomputes overlapping subproblems, giving O(φⁿ) calls. Memoize or iterate.

Explore the code comparison

Don't write this

def fib(self, n: int) -> int:
    if n < 2:
        return n
    return self.fib(n - 1) + self.fib(n - 2)   # exponential

Write this instead

def fib(self, n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Off-by-one on the return value

After n rolls of (a, b) = (b, a+b), a holds F(n) and b holds F(n+1). Returning b shifts every answer up by one.

Explore the code comparison

Don't write this

long a = 0, b = 1;
for (int i = 0; i < n; i++) {
    long next = a + b; a = b; b = next;
}
return b;   // this is F(n+1)

Write this instead

long a = 0, b = 1;
for (int i = 0; i < n; i++) {
    long next = a + b; a = b; b = next;
}
return a;

Silent long overflow

F(93) exceeds Long.MAX_VALUE, so the addition wraps to a wrong value. Use BigInteger when n can exceed 92.

Explore the code comparison

Don't write this

long a = 0, b = 1;          // wrong for n >= 93
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
return a;

Write this instead

BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
for (int i = 0; i < n; i++) { BigInteger t = a.add(b); a = b; b = t; }
return a;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bottom-up two-variable iteration; fast doubling for O(log n)

Code pattern to memorize

# O(n) iterative
a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
return a

# O(log n) fast doubling identities
F(2k)   = F(k) * (2*F(k+1) - F(k))
F(2k+1) = F(k)^2 + F(k+1)^2

Rules to remember

1Never write naive recursion fib(n-1) + fib(n-2) — it's O(φⁿ) and recomputes the same values exponentially. Memoize or iterate.
2Pin down the indexing convention: this page uses F(0) = 0, F(1) = 1. Off-by-one here flips every answer.
3Fibonacci overflows fast — F(93) exceeds a signed 64-bit long. Use BigInteger (Java) for large n; Python ints are unbounded.
4The iterative version needs only two rolling variables, not a full DP array — O(1) space.
5Fast doubling beats matrix exponentiation in constant factors (no 2×2 multiplies) while sharing the same O(log n) bound.

Use this pattern when

Compute a single F(n) — iterative O(n) is the clean default
n is astronomically large and you need O(log n) → fast doubling / matrix power
Teaching the memoization-vs-tabulation progression in DP
Any linear recurrence where you only need the last few terms (roll the window)

Choose another pattern when

You need *all* F(0..n) → keep the array; don't recompute each
n is tiny and fixed → a lookup table is simplest
You need F(n) mod m for huge n → fast doubling under the modulus (Pisano period optional)

Interview takeaway

Fibonacci is the canonical 'naive recursion is exponential, but it collapses to O(n) with two variables and O(log n) with doubling' story. Showing that full ladder — and naming the overflow boundary — is what an interviewer is grading.

Continue

Transfer the pattern to another problem

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

Transferable patternLinear recurrence solved bottom-up (window rolling for O(1) space) and via index-halving identities for O(log n). The transferable instincts: collapse a DP array to the few terms the recurrence references, and recognize that linear recurrences have logarithmic shortcuts through matrix power or doubling.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

nCr mod p

Continue · Next problem

Segmented Sieve

mediumMath GeometryAsked very often

Nth Fibonacci Number

Math & Number Theory · 28 of 36 · 9 min

Return the n-th Fibonacci number, where F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2) for n ≥ 2.

Discuss how your approach scales as n grows and what happens to the return type.

In plain English

Examples

Example 1

Input: n = 0
Output: 0
Note: Base case F(0) = 0.

Example 2

Input: n = 10
Output: 55
Note: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 — F(10) = 55.

Example 3

Input: n = 93
Output: 12200160415121876738
Note: F(93) exceeds Long.MAX_VALUE (~9.2 × 10¹⁸), so a long-based answer overflows — BigInteger required.

Constraints

0 ≤ n ≤ 92 if the answer must fit in a signed 64-bit integer
0 ≤ n ≤ 10⁶ or beyond with BigInteger / arbitrary precision
Indexing: F(0) = 0, F(1) = 1

Clarifying questions4First question: What indexing — does F(0) = 0 or F(1) = 1 start the sequence?Explore questions

Q1.What indexing — does F(0) = 0 or F(1) = 1 start the sequence?
I'll use F(0) = 0, F(1) = 1. The convention matters because an off-by-one shifts every value; I'd confirm yours.
Q2.How large can n be?
If n stays under ~92, a long holds F(n). Beyond that I switch to BigInteger, or use fast doubling if n is huge.
Q3.Do you want F(n) exactly, or modulo something?
If it's F(n) mod m for enormous n, I'd run fast doubling under the modulus rather than computing the full number.
Q4.Is a single value needed, or the whole prefix?
If you need every F(0..n) I'd keep the array; for a single value the two-variable roll is enough.

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 recognize naive recursion is exponential, reach for the O(1)-space iterative form, and — for the medium bar — know that an O(log n) method exists and why.

Where candidates slip

Submitting exponential recursion, getting the F(0)/F(1) base case off by one, or overflowing a long around F(93) without noticing.

How to stand out

Walk the full ladder: exponential recursion → memoized O(n) → iterative O(n) O(1) space → fast doubling O(log n). State the overflow point and offer BigInteger.

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 Bottom-Up, Two Variables (Baseline)	`O(n)`	`O(1)`	The clean default — mention naive recursion is exponential, then jump straight to this O(1)-space loop.	Read
2	Fast Doubling (Optimal, O(log n))Optimal	`O(log n)`	`O(log n) recursion stack`	When n is astronomically large or the interviewer pushes past O(n). Cite the doubling identities.	Read

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 Bottom-Up, Two Variables (Baseline)

TimeO(n)SpaceO(1)

The clean default — mention naive recursion is exponential, then jump straight to this O(1)-space loop.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Naive recursion recomputes fib(n-2) over and over. What's the minimum history you actually need to produce the next term?

2Hint 2Explore hint

Just the previous two values. Carry a = F(i-1), b = F(i), and roll them forward n times.

3Hint 3Explore hint

Start a, b = 0, 1 and repeat a, b = b, a + b. After n rolls, a holds F(n).

A · Core idea

Build the sequence from the bottom, carrying only the two most recent values. Seed a = F(0) = 0 and b = F(1) = 1, then repeat (a, b) = (b, a + b) exactly n times; a then holds F(n).

B · Visual dry run

Interactive dry run

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

n = 6

Array state

roll 2

(a, b) = (1, 2)

[0]

[1]

a ↓

[2]

b ↓

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result8

C · Code with teaching comments

Reference implementation previewpublic long fib(int n) { if (n < 0) { throw new IllegalArgumentException("n must be non-negative"); } long a = 0, b = 1;Explore the full code

solution.javaJava

Iterative Bottom-Up, Two Variables (Baseline) — reference

4 teaching notes

1
public long fib(int n) {
2
    if (n < 0) {
3
        throw new IllegalArgumentException("n must be non-negative");
4
    }
5
    // Seed with F(0) and F(1). a will end up holding F(n).
6
    long a = 0, b = 1;
7
    // Exactly n rolls advance a from F(0) to F(n).
8
    for (int i = 0; i < n; i++) {
9
        long next = a + b;   // overflows a long past n = 92
10
        a = b;
11
        b = next;
12
    }
13
    // Return a, NOT b — the classic off-by-one is returning b (which is F(n+1)).
14
    return a;
15
}

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

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

ComplexityO(n) time, O(1) space — One loop of n iterations, each doing a constant-time addition and reassignment. Only two scalars are stored, so space is O(1) — no DP array needed.

E · Edge cases and pitfalls3Submitting exponential naive recursion.Explore edge cases

Pitfalls

Submitting exponential naive recursion.
Returning b instead of a (off-by-one — b is F(n+1)).
Overflowing a long at F(93) without noticing.

03.2

Approach 2 of 2 · Optimal

Fast Doubling (Optimal, O(log n))

TimeO(log n)SpaceO(log n) recursion stack

When n is astronomically large or the interviewer pushes past O(n). Cite the doubling identities.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The iterative method does n additions. Could you jump from F(k) straight to F(2k), halving the index each step like fast exponentiation?

2Hint 2Explore hint

Yes — there are identities expressing F(2k) and F(2k+1) purely in terms of F(k) and F(k+1).

3Hint 3Explore hint

Recurse on n >> 1 (n / 2), get (F(k), F(k+1)), then combine: F(2k) = F(k)·(2F(k+1) − F(k)), F(2k+1) = F(k)² + F(k+1)². Pick the right pair based on the low bit of n.

A · Core idea

The identities and why they work. From the matrix form of Fibonacci you can derive:

F(2k) = F(k) · (2·F(k+1) − F(k))
F(2k+1) = F(k)² + F(k+1)²

B · Visual dry run

Interactive dry run

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

n = 6 (binary 110)

Interactive diagram

Halving the index each level

n=0

Active call / nodeSupporting contextReturned stateNot active

Fast doubling processes the bits of n, so depth is log₂ n rather than n.

Final result8

C · Code with teaching comments

solution.javaJava

Fast Doubling (Optimal, O(log n)) — optimal

4 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fib(int n) {
4
    return fibPair(n)[0];
5
}
6
 
7
// returns {F(n), F(n+1)}
8
private BigInteger[] fibPair(int n) {
9
    if (n == 0) {
10
        return new BigInteger[]{BigInteger.ZERO, BigInteger.ONE};
11
    }
12
    // Recurse on n/2 — each level halves the index, giving O(log n) depth.
13
    BigInteger[] half = fibPair(n >> 1);
14
    BigInteger fk = half[0], fk1 = half[1];
15
    // F(2k) = F(k) * (2*F(k+1) - F(k))
16
    // F(2k) = F(k)·(2F(k+1) − F(k)); shiftLeft(1) is the ×2.
17
    BigInteger c = fk.multiply(fk1.shiftLeft(1).subtract(fk));
18
    // F(2k+1) = F(k)^2 + F(k+1)^2
19
    // F(2k+1) = F(k)² + F(k+1)².
20
    BigInteger d = fk.multiply(fk).add(fk1.multiply(fk1));
21
    if ((n & 1) == 0) {
22
        return new BigInteger[]{c, d};        // even index
23
    } else {
24
        return new BigInteger[]{d, c.add(d)}; // odd index: shift by one
25
    }
26
}

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

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

E · Edge cases and pitfalls6n = 0 — Base case returns the pair (0, 1); fib returns 0.Explore edge cases

Edge cases handled

n = 0Base case returns the pair (0, 1); fib returns 0.
n = 1Recurses to n=0, doubles+shifts to (1, 1); returns 1.
n = 93Exceeds a long; BigInteger returns the exact 12200160415121876738.

Pitfalls

Mixing up which identity is F(2k) vs F(2k+1).
Forgetting the odd-bit shift, landing one index off.
Claiming flat O(log n) for big n — the BigInteger multiplies themselves grow.

Practice

Try the solution yourself

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

Editable code previewimport java.math.BigInteger; public BigInteger fib(int n) { return fibPair(n)[0]; }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.

Exponential naive recursion

fib(n-1) + fib(n-2) recomputes overlapping subproblems, giving O(φⁿ) calls. Memoize or iterate.

Explore the code comparison

Don't write this

def fib(self, n: int) -> int:
    if n < 2:
        return n
    return self.fib(n - 1) + self.fib(n - 2)   # exponential

Write this instead

def fib(self, n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Off-by-one on the return value

After n rolls of (a, b) = (b, a+b), a holds F(n) and b holds F(n+1). Returning b shifts every answer up by one.

Explore the code comparison

Don't write this

long a = 0, b = 1;
for (int i = 0; i < n; i++) {
    long next = a + b; a = b; b = next;
}
return b;   // this is F(n+1)

Write this instead

long a = 0, b = 1;
for (int i = 0; i < n; i++) {
    long next = a + b; a = b; b = next;
}
return a;

Silent long overflow

F(93) exceeds Long.MAX_VALUE, so the addition wraps to a wrong value. Use BigInteger when n can exceed 92.

Explore the code comparison

Don't write this

long a = 0, b = 1;          // wrong for n >= 93
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
return a;

Write this instead

BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
for (int i = 0; i < n; i++) { BigInteger t = a.add(b); a = b; b = t; }
return a;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bottom-up two-variable iteration; fast doubling for O(log n)

Code pattern to memorize

# O(n) iterative
a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
return a

# O(log n) fast doubling identities
F(2k)   = F(k) * (2*F(k+1) - F(k))
F(2k+1) = F(k)^2 + F(k+1)^2

Rules to remember

1Never write naive recursion fib(n-1) + fib(n-2) — it's O(φⁿ) and recomputes the same values exponentially. Memoize or iterate.
2Pin down the indexing convention: this page uses F(0) = 0, F(1) = 1. Off-by-one here flips every answer.
3Fibonacci overflows fast — F(93) exceeds a signed 64-bit long. Use BigInteger (Java) for large n; Python ints are unbounded.
4The iterative version needs only two rolling variables, not a full DP array — O(1) space.
5Fast doubling beats matrix exponentiation in constant factors (no 2×2 multiplies) while sharing the same O(log n) bound.

Use this pattern when

Compute a single F(n) — iterative O(n) is the clean default
n is astronomically large and you need O(log n) → fast doubling / matrix power
Teaching the memoization-vs-tabulation progression in DP
Any linear recurrence where you only need the last few terms (roll the window)

Choose another pattern when

You need *all* F(0..n) → keep the array; don't recompute each
n is tiny and fixed → a lookup table is simplest
You need F(n) mod m for huge n → fast doubling under the modulus (Pisano period optional)

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

Same pattern

←

nCr mod p

Continue · Next problem

Segmented Sieve