Loading…

mediumDynamic ProgrammingSometimes asked

Fibonacci Modified

Q: How do you solve Fibonacci Modified using the Brute Force — Plain Recursion (Exponential) approach?

When to use it: State it to confirm the recurrence, then point out the exponential recomputation that motivates a simple forward scan. The literal translation: `t(i) = t(i-2) + t(i-1)²` with base cases `t(1) = t1`, `t(2) = t2`. Compute `t(i-1)`, square it, add `t(i-2)`. **Why it's correct.** It mirrors the definition exactly, so the value is right. **Why it's wasteful.** Like ordinary Fibonacci, the two recursive branches overlap: `t(i-1)` itself needs `t(i-2)`, which is then computed again by the sibling branch. The call tree is exponential in `n`. For ordinary Fibonacci that's already bad; here it's worse because every node performs a big-integer **square** on numbers with up to thousands of digits. **The fix is trivial.** There's no reason to recurse — the terms are produced strictly left to right. Sweeping forward once and keeping the last two terms computes each value exactly once. That's the optimal approach below. Time complexity: O(2^n) big-integer ops. Space complexity: O(n) recursion stack (plus huge numbers).

Q: How do you solve Fibonacci Modified using the Iterative Forward Scan with BigInteger (Optimal) approach?

When to use it: The answer they want. Phrase it as 'walk forward from term 3, each new term = two-back + previous², all in BigInteger'. The terms come out in order, so just compute them in order. Keep two running values: `prev` = t(i-1) and `prevPrev` = t(i-2). For each `i` from 3 to n: 1. `cur = prevPrev + prev²`. 2. Slide the window: `prevPrev = prev`, `prev = cur`. After the loop, `prev` holds t_n. **Why BigInteger is non-negotiable.** The digit count roughly doubles each step. Even with the tiny seeds `0, 1`, term 10 has 23 digits and term 20 has well over a thousand — vastly beyond `long`'s 19-digit ceiling. `double` would round away exactness almost immediately. Java's `BigInteger` and Python's arbitrary-precision `int` store the exact value regardless of size. **Why O(1) terms but not O(1) work.** We only ever keep two previous values, so memory in *terms* is constant — but each term is a giant number, and squaring two k-digit numbers costs more than O(1). The honest complexity is 'n iterations of big-integer arithmetic', with the final squares dominating. **Correctness.** Each term is computed exactly once from its true predecessors, directly implementing the definition. Time complexity: O(n) big-integer multiplies. Space complexity: O(1) terms (numbers themselves are huge).

Dynamic Programming · 41 of 44 · 9 min

A modified Fibonacci sequence is defined by:

t(i+2) = t(i) + (t(i+1))²

Given three integers t1, t2, and n, compute and return the n-th term of the sequence (1-indexed), where t1 and t2 are the first two terms.

In plain English

Each term is built from the two before it, but unlike ordinary Fibonacci the nearer term is squared. The sequence therefore grows far faster than ordinary exponential: the number of digits roughly doubles every step. The algorithm is a trivial forward scan; the entire difficulty is numeric — choosing a type that can hold values with thousands of digits exactly. That means BigInteger in Java and Python's unbounded int.

Examples

Example 1

Input: t1 = 0, t2 = 1, n = 5
Output: 5
Note: t3 = 0 + 1² = 1; t4 = 1 + 1² = 2; t5 = 1 + 2² = 5.

Example 2

Input: t1 = 0, t2 = 1, n = 6
Output: 27
Note: Continuing: t6 = t4 + t5² = 2 + 5² = 27.

Example 3

Input: t1 = 2, t2 = 0, n = 4
Output: 4
Note: t3 = t1 + t2² = 2 + 0² = 2; t4 = t2 + t3² = 0 + 2² = 4.

Example 4

Input: t1 = 0, t2 = 1, n = 10
Output: 84266613096281243382112
Note: By the 10th term the value already has 23 digits — far beyond a 64-bit long — illustrating why BigInteger is required.

Constraints

0 ≤ t1, t2 ≤ 2
3 ≤ n ≤ 20
The terms grow doubly-exponentially — the n-th term can have thousands of digits
Return the exact value (arbitrary precision); no modulus is applied

Clarifying questions4First question: Which term is squared — the previous one or the one two back?Explore questions

Q1.Which term is squared — the previous one or the one two back?
The previous term, t(i+1), is squared; t(i) (two positions back) is added unsquared. Misreading this is the #1 logic error.
Q2.Is the sequence 1-indexed or 0-indexed?
1-indexed: t1 and t2 are the first two terms, and we want t_n. The loop generates t3 through t_n.
Q3.Is there a modulus, or do we need the exact full value?
The exact value — no modulus. That's precisely why arbitrary-precision integers are mandatory; the result can have thousands of digits.
Q4.Can I use long or double?
No. long overflows by around the 10th term, and double loses integer precision almost immediately. Use BigInteger / Python int.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Given the first two terms t₁ and t₂, the sequence is defined by t(i+2) = t(i) + t(i+1)². So each new term is the term two back plus the SQUARE of the previous term. Iterate from term 3 up to term n, carrying the last two values. The squaring makes the numbers grow doubly-exponentially, so the values overflow 64-bit integers within a dozen terms — you MUST use arbitrary-precision integers (Java BigInteger, Python's native int). O(n) iterations, each doing one big-integer multiply.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you parse the recurrence correctly (square the previous term, add the one two back) and immediately recognise that the explosive growth demands arbitrary-precision integers rather than fixed-width types.

Where candidates slip

Using long/int and overflowing within ~10 terms, squaring the wrong term, or using double and losing exact integer precision.

How to stand out

Call out the doubly-exponential growth before writing code, justify BigInteger, note that only two terms must be retained, and mention that the big-multiply cost (not the loop) dominates the complexity.

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	Brute Force — Plain Recursion (Exponential)	`O(2^n) big-integer ops`	`O(n) recursion stack (plus huge numbers)`	State it to confirm the recurrence, then point out the exponential recomputation that motivates a simple forward scan.	Read
2	Iterative Forward Scan with BigInteger (Optimal)Optimal	`O(n) big-integer multiplies`	`O(1) terms (numbers themselves are huge)`	The answer they want. Phrase it as 'walk forward from term 3, each new term = two-back + previous², all in BigInteger'.	Read

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

The recurrence wiring

How to read it:The previous term is squared; the term two back is added directly.

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

Brute Force — Plain Recursion (Exponential)

TimeO(2^n) big-integer opsSpaceO(n) recursion stack (plus huge numbers)

State it to confirm the recurrence, then point out the exponential recomputation that motivates a simple forward scan.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write t(i) = t(i-2) + t(i-1)² directly as a recursion, with t(1)=t1 and t(2)=t2 as base cases.

2Hint 2Explore hint

Each call to t(i) recurses into t(i-1) and t(i-2) — and t(i-1) recurses into t(i-2) again, so the same term is recomputed many times.

3Hint 3Explore hint

Use BigInteger even here: the values are gigantic regardless of how you compute them.

A · Core idea

The literal translation: t(i) = t(i-2) + t(i-1)² with base cases t(1) = t1, t(2) = t2. Compute t(i-1), square it, add t(i-2).

Why it's correct. It mirrors the definition exactly, so the value is right.

Why it's wasteful. Like ordinary Fibonacci, the two recursive branches overlap: t(i-1) itself needs t(i-2), which is then computed again by the sibling branch. The call tree is exponential in n. For ordinary Fibonacci that's already bad; here it's worse because every node performs a big-integer square on numbers with up to thousands of digits.

The fix is trivial. There's no reason to recurse — the terms are produced strictly left to right. Sweeping forward once and keeping the last two terms computes each value exactly once. That's the optimal approach below.

B · Visual dry run

Interactive dry run

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

t1 = 0, t2 = 1, n = 5

Interactive diagram

Overlapping recursion

t(5)

Active call / nodeSupporting contextReturned stateNot active

t(3) is computed along two separate branches — the redundancy DP removes.

Final result5

C · Code with teaching comments

Reference implementation previewimport java.math.BigInteger; public BigInteger fibonacciModified(int t1, int t2, int n) { return term(BigInteger.valueOf(t1), BigInteger.valueOf(t2), n); }Explore the full code

solution.javaJava

Brute Force — Plain Recursion (Exponential) — reference

3 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fibonacciModified(int t1, int t2, int n) {
4
    return term(BigInteger.valueOf(t1), BigInteger.valueOf(t2), n);
5
}
6
 
7
private BigInteger term(BigInteger t1, BigInteger t2, int i) {
8
    // Base case: first seed term.
9
    if (i == 1) return t1;
10
    if (i == 2) return t2;
11
    // The term to be squared.
12
    BigInteger prev = term(t1, t2, i - 1);
13
    BigInteger prevPrev = term(t1, t2, i - 2);
14
    // t(i) = t(i-2) + t(i-1)² in BigInteger arithmetic.
15
    return prevPrev.add(prev.multiply(prev));
16
}

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

D · Why it works and complexityO(2^n) big-integer ops timeO(n) recursion stack (plus huge numbers) spaceOpen the invariant and proofExplore the proof

Even a non-linear recurrence (the squared term) still only depends on the two prior terms, so the exponential recursion is pure waste. Recognising the fixed two-term window is what collapses it to a single forward pass.

ComplexityO(2^n) big-integer ops time, O(n) recursion stack (plus huge numbers) space — Each call spawns two recursive calls (one of them squared), giving an exponential number of calls — and every arithmetic op is on huge numbers, compounding the cost.

E · Edge cases and pitfalls3Using int/long inside the recursion — overflow corrupts the result silently.Explore edge cases

Pitfalls

Using int/long inside the recursion — overflow corrupts the result silently.
Squaring t(i-2) instead of t(i-1).
Recursing at all — exponential big-integer work when a single forward pass suffices.

03.2

Approach 2 of 2 · Optimal

Iterative Forward Scan with BigInteger (Optimal)

TimeO(n) big-integer multipliesSpaceO(1) terms (numbers themselves are huge)

The answer they want. Phrase it as 'walk forward from term 3, each new term = two-back + previous², all in BigInteger'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate terms left to right starting from the two seeds; you never need to look back more than two terms.

2Hint 2Explore hint

Each step: next = twoBack + prev·prev, then shift the window forward.

3Hint 3Explore hint

Hold every value in BigInteger (Java) / int (Python). Squaring is BigInteger.multiply(self).

A · Core idea

The terms come out in order, so just compute them in order. Keep two running values: prev = t(i-1) and prevPrev = t(i-2). For each i from 3 to n:

1
cur = prevPrev + prev².
2
Slide the window: prevPrev = prev, prev = cur.

After the loop, prev holds t_n.

Why BigInteger is non-negotiable. The digit count roughly doubles each step. Even with the tiny seeds 0, 1, term 10 has 23 digits and term 20 has well over a thousand — vastly beyond long's 19-digit ceiling. double would round away exactness almost immediately. Java's BigInteger and Python's arbitrary-precision int store the exact value regardless of size.

Why O(1) terms but not O(1) work. We only ever keep two previous values, so memory in terms is constant — but each term is a giant number, and squaring two k-digit numbers costs more than O(1). The honest complexity is 'n iterations of big-integer arithmetic', with the final squares dominating.

Correctness. Each term is computed exactly once from its true predecessors, directly implementing the definition.

B · Visual dry run

Interactive dry run

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

t1 = 0, t2 = 1, n = 6

Array state

init

prevPrev=0, prev=1

[0]

[1]

Current pointerResolved stateNot processed

Final result27

C · Code with teaching comments

solution.javaJava

Iterative Forward Scan with BigInteger (Optimal) — optimal

4 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fibonacciModified(int t1, int t2, int n) {
4
    // t(i-2) window value, seeded with t1.
5
    BigInteger prevPrev = BigInteger.valueOf(t1);
6
    BigInteger prev = BigInteger.valueOf(t2);
7
    for (int i = 3; i <= n; i++) {
8
        // t(i) = t(i-2) + t(i-1)²; multiply(prev) squares prev exactly.
9
        BigInteger cur = prevPrev.add(prev.multiply(prev));
10
        // Slide the window forward by one term.
11
        prevPrev = prev;
12
        prev = cur;
13
    }
14
    // After the loop, prev holds t_n.
15
    return prev;
16
}

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

D · Why it works and complexityO(n) big-integer multiplies timeO(1) terms (numbers themselves are huge) spaceOpen the invariant and proofExplore the proof

The whole problem is a type-selection problem dressed up as a recurrence. Once you commit to BigInteger and carry just the two-term window, the algorithm is a five-line loop — the interviewer is watching whether you anticipate the overflow, not whether you can write the loop.

ComplexityO(n) big-integer multiplies time, O(1) terms (numbers themselves are huge) space — n−2 iterations, each performing one big-integer square and add. The arithmetic cost grows with the digit count, so the big-multiply dominates; the loop count itself is linear in n.

E · Edge cases and pitfalls6t1 = 0, t2 = 1, n = 3 — One iteration: cur = 0 + 1² = 1 → returns 1.Explore edge cases

Edge cases handled

t1 = 0, t2 = 1, n = 3One iteration: cur = 0 + 1² = 1 → returns 1.
t1 = 2, t2 = 0, n = 4t3 = 2 + 0² = 2; t4 = 0 + 2² = 4 → returns 4.
t1 = 0, t2 = 2, n = 4t3 = 0 + 2² = 4; t4 = 2 + 4² = 18 → returns 18.

Pitfalls

Using long/int — overflows around term 10, producing a wrong but plausible-looking number.
Squaring with double (prev*prev as floating point) — loses exact integer precision.
Shifting the window before using both values, e.g. overwriting prevPrev too early.

Practice

Try the solution yourself

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

Editable code previewimport java.math.BigInteger; public BigInteger fibonacciModified(int t1, int t2, int n) { BigInteger prevPrev = BigInteger.valueOf(t1); BigInteger prev = BigInteger.valueOf(t2);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.

Overflow from fixed-width integers

The values grow doubly-exponentially; by term ~10 they exceed 64-bit range. long silently wraps and the answer is garbage even though the loop looks correct.

Explore the code comparison

Don't write this

long prevPrev = t1, prev = t2;
for (int i = 3; i <= n; i++) {
    long cur = prevPrev + prev * prev;  // overflows fast
    prevPrev = prev; prev = cur;
}

Write this instead

BigInteger prevPrev = BigInteger.valueOf(t1), prev = BigInteger.valueOf(t2);
for (int i = 3; i <= n; i++) {
    BigInteger cur = prevPrev.add(prev.multiply(prev));
    prevPrev = prev; prev = cur;
}

Squaring the wrong term

The definition squares the PREVIOUS term t(i-1), not the one two back. Squaring t(i-2) computes a different sequence entirely.

Explore the code comparison

Don't write this

cur = prev + prev_prev * prev_prev  # squared the wrong term

Write this instead

cur = prev_prev + prev * prev      # square t(i-1), add t(i-2)

Floating-point arithmetic

double can hold large magnitudes but only ~15–16 significant digits. The exact integer value is lost almost immediately, so the printed result is wrong.

Explore the code comparison

Don't write this

double cur = prevPrev + prev * prev;  // precision lost

Write this instead

BigInteger cur = prevPrev.add(prev.multiply(prev));  // exact

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Linear-scan recurrence with a squared term → arbitrary-precision arithmetic

Code pattern to memorize

t1, t2 given
for i in 3..n:
    t_i = t_{i-2} + (t_{i-1})²
return t_n

Rules to remember

1The recurrence is t(i+2) = t(i) + t(i+1)² — the previous term is squared, the one two back is added as-is. Don't swap them.
2Growth is doubly-exponential (digit count roughly doubles each step), so by n ≈ 20 the value has thousands of digits — long/int overflow silently.
3Use BigInteger (Java) or Python's built-in int; never long, double, or float (floats lose precision instantly).
4It's 1-indexed: t₁ and t₂ are the seeds, the loop starts producing t₃.
5Only two previous terms are ever needed → O(1) extra big-integers beyond the current value.

Use this pattern when

A recurrence references a fixed window of previous terms
Terms involve multiplication/squaring → values explode beyond machine integers
n is small but each value is enormous (big-integer territory)
You can carry just the last k terms instead of the whole table

Choose another pattern when

An answer modulo some prime is requested → use modular arithmetic, BigInteger unnecessary
Terms stay bounded (no multiplication) → plain long is fine
You need the term for huge n with a *linear* recurrence → matrix exponentiation (doesn't apply: squaring is non-linear)
Floating tolerance acceptable → still no, integer exactness is required here

Interview takeaway

When a recurrence squares or multiplies previous terms, the bottleneck stops being the loop and becomes the size of the numbers. Reach for BigInteger immediately, carry only the window of terms you need, and the problem is a few lines.

Continue

Transfer the pattern to another problem

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

Transferable patternWhen a recurrence multiplies or squares previous terms, growth turns doubly-exponential and the real constraint is numeric range, not loop count. Reach for arbitrary-precision integers (BigInteger / Python int), carry only the fixed window of prior terms, and the solution is a short forward scan.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Fibonacci Modified (memoised DP variant)
Same recurrence framed as a top-down memoised table — caches each term once.
Fibonacci Number
Coming soon
The unsquared base case — values stay small, so long suffices.
Climbing Stairs
Another two-term linear recurrence; contrast its bounded growth with this one's explosion.

Same pattern

←

Decibinary Numbers

Continue · Next problem

Gena Playing Hanoi

mediumDynamic ProgrammingSometimes asked

Fibonacci Modified

Dynamic Programming · 41 of 44 · 9 min

A modified Fibonacci sequence is defined by:

t(i+2) = t(i) + (t(i+1))²

Given three integers t1, t2, and n, compute and return the n-th term of the sequence (1-indexed), where t1 and t2 are the first two terms.

In plain English

Examples

Example 1

Input: t1 = 0, t2 = 1, n = 5
Output: 5
Note: t3 = 0 + 1² = 1; t4 = 1 + 1² = 2; t5 = 1 + 2² = 5.

Example 2

Input: t1 = 0, t2 = 1, n = 6
Output: 27
Note: Continuing: t6 = t4 + t5² = 2 + 5² = 27.

Example 3

Input: t1 = 2, t2 = 0, n = 4
Output: 4
Note: t3 = t1 + t2² = 2 + 0² = 2; t4 = t2 + t3² = 0 + 2² = 4.

Example 4

Input: t1 = 0, t2 = 1, n = 10
Output: 84266613096281243382112
Note: By the 10th term the value already has 23 digits — far beyond a 64-bit long — illustrating why BigInteger is required.

Constraints

0 ≤ t1, t2 ≤ 2
3 ≤ n ≤ 20
The terms grow doubly-exponentially — the n-th term can have thousands of digits
Return the exact value (arbitrary precision); no modulus is applied

Clarifying questions4First question: Which term is squared — the previous one or the one two back?Explore questions

Q1.Which term is squared — the previous one or the one two back?
The previous term, t(i+1), is squared; t(i) (two positions back) is added unsquared. Misreading this is the #1 logic error.
Q2.Is the sequence 1-indexed or 0-indexed?
1-indexed: t1 and t2 are the first two terms, and we want t_n. The loop generates t3 through t_n.
Q3.Is there a modulus, or do we need the exact full value?
The exact value — no modulus. That's precisely why arbitrary-precision integers are mandatory; the result can have thousands of digits.
Q4.Can I use long or double?
No. long overflows by around the 10th term, and double loses integer precision almost immediately. Use BigInteger / Python int.

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

Where candidates slip

Using long/int and overflowing within ~10 terms, squaring the wrong term, or using double and losing exact integer precision.

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	Brute Force — Plain Recursion (Exponential)	`O(2^n) big-integer ops`	`O(n) recursion stack (plus huge numbers)`	State it to confirm the recurrence, then point out the exponential recomputation that motivates a simple forward scan.	Read
2	Iterative Forward Scan with BigInteger (Optimal)Optimal	`O(n) big-integer multiplies`	`O(1) terms (numbers themselves are huge)`	The answer they want. Phrase it as 'walk forward from term 3, each new term = two-back + previous², all in BigInteger'.	Read

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

The recurrence wiring

How to read it:The previous term is squared; the term two back is added directly.

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

Brute Force — Plain Recursion (Exponential)

TimeO(2^n) big-integer opsSpaceO(n) recursion stack (plus huge numbers)

State it to confirm the recurrence, then point out the exponential recomputation that motivates a simple forward scan.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write t(i) = t(i-2) + t(i-1)² directly as a recursion, with t(1)=t1 and t(2)=t2 as base cases.

2Hint 2Explore hint

Each call to t(i) recurses into t(i-1) and t(i-2) — and t(i-1) recurses into t(i-2) again, so the same term is recomputed many times.

3Hint 3Explore hint

Use BigInteger even here: the values are gigantic regardless of how you compute them.

A · Core idea

The literal translation: t(i) = t(i-2) + t(i-1)² with base cases t(1) = t1, t(2) = t2. Compute t(i-1), square it, add t(i-2).

Why it's correct. It mirrors the definition exactly, so the value is right.

B · Visual dry run

Interactive dry run

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

t1 = 0, t2 = 1, n = 5

Interactive diagram

Overlapping recursion

t(5)

Active call / nodeSupporting contextReturned stateNot active

t(3) is computed along two separate branches — the redundancy DP removes.

Final result5

C · Code with teaching comments

solution.javaJava

Brute Force — Plain Recursion (Exponential) — reference

3 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fibonacciModified(int t1, int t2, int n) {
4
    return term(BigInteger.valueOf(t1), BigInteger.valueOf(t2), n);
5
}
6
 
7
private BigInteger term(BigInteger t1, BigInteger t2, int i) {
8
    // Base case: first seed term.
9
    if (i == 1) return t1;
10
    if (i == 2) return t2;
11
    // The term to be squared.
12
    BigInteger prev = term(t1, t2, i - 1);
13
    BigInteger prevPrev = term(t1, t2, i - 2);
14
    // t(i) = t(i-2) + t(i-1)² in BigInteger arithmetic.
15
    return prevPrev.add(prev.multiply(prev));
16
}

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

D · Why it works and complexityO(2^n) big-integer ops timeO(n) recursion stack (plus huge numbers) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Using int/long inside the recursion — overflow corrupts the result silently.Explore edge cases

Pitfalls

Using int/long inside the recursion — overflow corrupts the result silently.
Squaring t(i-2) instead of t(i-1).
Recursing at all — exponential big-integer work when a single forward pass suffices.

03.2

Approach 2 of 2 · Optimal

Iterative Forward Scan with BigInteger (Optimal)

TimeO(n) big-integer multipliesSpaceO(1) terms (numbers themselves are huge)

The answer they want. Phrase it as 'walk forward from term 3, each new term = two-back + previous², all in BigInteger'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate terms left to right starting from the two seeds; you never need to look back more than two terms.

2Hint 2Explore hint

Each step: next = twoBack + prev·prev, then shift the window forward.

3Hint 3Explore hint

Hold every value in BigInteger (Java) / int (Python). Squaring is BigInteger.multiply(self).

A · Core idea

The terms come out in order, so just compute them in order. Keep two running values: prev = t(i-1) and prevPrev = t(i-2). For each i from 3 to n:

1
cur = prevPrev + prev².
2
Slide the window: prevPrev = prev, prev = cur.

After the loop, prev holds t_n.

Correctness. Each term is computed exactly once from its true predecessors, directly implementing the definition.

B · Visual dry run

Interactive dry run

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

t1 = 0, t2 = 1, n = 6

Array state

init

prevPrev=0, prev=1

[0]

[1]

Current pointerResolved stateNot processed

Final result27

C · Code with teaching comments

solution.javaJava

Iterative Forward Scan with BigInteger (Optimal) — optimal

4 teaching notes

1
import java.math.BigInteger;
2
 
3
public BigInteger fibonacciModified(int t1, int t2, int n) {
4
    // t(i-2) window value, seeded with t1.
5
    BigInteger prevPrev = BigInteger.valueOf(t1);
6
    BigInteger prev = BigInteger.valueOf(t2);
7
    for (int i = 3; i <= n; i++) {
8
        // t(i) = t(i-2) + t(i-1)²; multiply(prev) squares prev exactly.
9
        BigInteger cur = prevPrev.add(prev.multiply(prev));
10
        // Slide the window forward by one term.
11
        prevPrev = prev;
12
        prev = cur;
13
    }
14
    // After the loop, prev holds t_n.
15
    return prev;
16
}

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

D · Why it works and complexityO(n) big-integer multiplies timeO(1) terms (numbers themselves are huge) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6t1 = 0, t2 = 1, n = 3 — One iteration: cur = 0 + 1² = 1 → returns 1.Explore edge cases

Edge cases handled

t1 = 0, t2 = 1, n = 3One iteration: cur = 0 + 1² = 1 → returns 1.
t1 = 2, t2 = 0, n = 4t3 = 2 + 0² = 2; t4 = 0 + 2² = 4 → returns 4.
t1 = 0, t2 = 2, n = 4t3 = 0 + 2² = 4; t4 = 2 + 4² = 18 → returns 18.

Pitfalls

Using long/int — overflows around term 10, producing a wrong but plausible-looking number.
Squaring with double (prev*prev as floating point) — loses exact integer precision.
Shifting the window before using both values, e.g. overwriting prevPrev too early.

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.

Overflow from fixed-width integers

The values grow doubly-exponentially; by term ~10 they exceed 64-bit range. long silently wraps and the answer is garbage even though the loop looks correct.

Explore the code comparison

Don't write this

long prevPrev = t1, prev = t2;
for (int i = 3; i <= n; i++) {
    long cur = prevPrev + prev * prev;  // overflows fast
    prevPrev = prev; prev = cur;
}

Write this instead

BigInteger prevPrev = BigInteger.valueOf(t1), prev = BigInteger.valueOf(t2);
for (int i = 3; i <= n; i++) {
    BigInteger cur = prevPrev.add(prev.multiply(prev));
    prevPrev = prev; prev = cur;
}

Squaring the wrong term

The definition squares the PREVIOUS term t(i-1), not the one two back. Squaring t(i-2) computes a different sequence entirely.

Explore the code comparison

Don't write this

cur = prev + prev_prev * prev_prev  # squared the wrong term

Write this instead

cur = prev_prev + prev * prev      # square t(i-1), add t(i-2)

Floating-point arithmetic

double can hold large magnitudes but only ~15–16 significant digits. The exact integer value is lost almost immediately, so the printed result is wrong.

Explore the code comparison

Don't write this

double cur = prevPrev + prev * prev;  // precision lost

Write this instead

BigInteger cur = prevPrev.add(prev.multiply(prev));  // exact

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Linear-scan recurrence with a squared term → arbitrary-precision arithmetic

Code pattern to memorize

t1, t2 given
for i in 3..n:
    t_i = t_{i-2} + (t_{i-1})²
return t_n

Rules to remember

1The recurrence is t(i+2) = t(i) + t(i+1)² — the previous term is squared, the one two back is added as-is. Don't swap them.
2Growth is doubly-exponential (digit count roughly doubles each step), so by n ≈ 20 the value has thousands of digits — long/int overflow silently.
3Use BigInteger (Java) or Python's built-in int; never long, double, or float (floats lose precision instantly).
4It's 1-indexed: t₁ and t₂ are the seeds, the loop starts producing t₃.
5Only two previous terms are ever needed → O(1) extra big-integers beyond the current value.

Use this pattern when

A recurrence references a fixed window of previous terms
Terms involve multiplication/squaring → values explode beyond machine integers
n is small but each value is enormous (big-integer territory)
You can carry just the last k terms instead of the whole table

Choose another pattern when

An answer modulo some prime is requested → use modular arithmetic, BigInteger unnecessary
Terms stay bounded (no multiplication) → plain long is fine
You need the term for huge n with a *linear* recurrence → matrix exponentiation (doesn't apply: squaring is non-linear)
Floating tolerance acceptable → still no, integer exactness is required here

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

Fibonacci Modified (memoised DP variant)
Same recurrence framed as a top-down memoised table — caches each term once.
Fibonacci Number
Coming soon
The unsquared base case — values stay small, so long suffices.
Climbing Stairs
Another two-term linear recurrence; contrast its bounded growth with this one's explosion.

Same pattern

←

Decibinary Numbers

Continue · Next problem

Gena Playing Hanoi