Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Compute the term tₙ of a Fibonacci-like sequence where each term is the previous term plus the square of the term before it: t(i+2) = t(i) + t(i+1)². Given t₁, t₂, and n, iterate the recurrence forward keeping just the last two terms. The catch is magnitude: squaring makes the values grow doubly-exponentially, so by n ≈ 20 they have thousands of digits — you MUST use arbitrary-precision integers (Java BigInteger; Python ints are unbounded natively). O(n) iterations, but each multiplication is expensive because the operands are huge.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that the squared term causes explosive growth requiring arbitrary-precision integers, and that the recurrence itself is a simple two-variable forward iteration.
Where candidates slip
Using long/int and silently overflowing, or squaring the wrong (older) term, or mishandling the 1-indexing so the loop runs one step too few or too many.
How to stand out
Call out the doubly-exponential growth, justify BigInteger immediately, and collapse to two rolling variables — then note Python needs no special type.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Adding the older term to the square of the newer term drives doubly-exponential growth.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Naive Recursion
1Hint 1Explore hintHide hint
Translate the recurrence literally: t(i) = t(i-2) + t(i-1)², with base cases t(1) and t(2).
2Hint 2Explore hintHide hint
Each call spawns two calls (for i-1 and i-2), so the call tree is exponential even though only n distinct terms exist.
3Hint 3Explore hintHide hint
Use BigInteger in Java for the arithmetic — even the small-index terms become large fast.
A · Core idea
Write the recurrence as a function. t(i) = t(i−2) + t(i−1)², with t(1) = t₁ and t(2) = t₂. Recurse down to the base cases.
Why it's correct. It's a direct transcription of the definition; every term is built from the two before it.
Why it recomputes. Computing t(i) calls t(i−1) and t(i−2); t(i−1) in turn calls t(i−2) again, and so on — the same term is evaluated exponentially many times. There are only n distinct terms, so this redundancy is pure waste.
Why it still 'works' here. Because n ≤ 20, even 2²⁰ ≈ 10⁶ calls finish, so the naive version technically passes. But it teaches the wrong instinct: the moment n grew, it would blow up — and it's trivially fixable. The arithmetic is on BigInteger regardless, because the terms are large even at small indices.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
t₁ = 0, t₂ = 1, n = 5Interactive diagram
Exponential call tree
t(3)t(3) is computed multiple times — the redundancy memoization removes.
5C · Code with teaching comments
Reference implementation previewimport java.math.BigInteger; public BigInteger fibonacciModified(int t1, int t2, int n) { return t(n, BigInteger.valueOf(t1), BigInteger.valueOf(t2)); }Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) calls timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Even with only n terms, naive recursion re-derives each one exponentially often. Recognising 'few distinct terms, recomputed repeatedly' points straight to memoization or, better, a single forward loop.
ComplexityO(2ⁿ) calls time, O(n) space — Two recursive calls per term build a binary tree with ~2ⁿ nodes; depth O(n). (Each arithmetic op is also expensive due to big operands.)
E · Edge cases and pitfalls3Squaring t(i-2) instead of t(i-1).Explore edge casesHide edge cases
Pitfalls
- Squaring t(i-2) instead of t(i-1).
- Using long instead of BigInteger in Java — overflow.
- Assuming small n makes recursion fine in general — it doesn't scale.
Approach 2 of 2 · Optimal
Iterative Two-Variable DP (Optimal)
1Hint 1Explore hintHide hint
Keep just the last two terms, prev and cur, starting at t₁ and t₂.
2Hint 2Explore hintHide hint
Each step: the new term is prev + cur² (older + newer²); then shift prev ← cur, cur ← new.
3Hint 3Explore hintHide hint
Loop from index 3 to n. In Java the operands are BigInteger; in Python plain ints.
A · Core idea
Iterate the recurrence forward, carrying only the two terms it depends on.
State. prev = t(i−1) and cur = t(i). Initialise prev = t₁, cur = t₂ (the two seeds). Each iteration computes the next term next = prev + cur², then slides the window: prev ← cur, cur ← next.
Loop bounds. The seeds are t₁, t₂, so the first computed term is t₃. Run the loop for index 3 through n; after it finishes, cur holds tₙ. If n == 1 return t₁, if n == 2 return t₂ (guard the seeds).
The real challenge: magnitude. Squaring roughly doubles the digit count each step, so the numbers grow doubly-exponentially. By n = 20 a term can have on the order of thousands of digits. A 64-bit long overflows within the first few steps and gives silent garbage. Use `BigInteger` in Java; Python's int is arbitrary precision, so no special type is needed.
Cost note. Although there are only O(n) iterations, each BigInteger multiplication operates on increasingly large operands, so the bit complexity is higher than O(n). For n ≤ 20 this is irrelevant, but it's worth stating that the squaring, not the loop length, dominates real runtime.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
t₁ = 0, t₂ = 1, n = 6Array state
i=3
prev=1, cur=1
27C · Code with teaching comments
D · Why it works and complexityO(n) iterations timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The recurrence reaches back exactly two terms, so two rolling variables replace any array — the same compression as Fibonacci. The twist is that 'O(1) space' here means two variables, each of which may hold a number with thousands of digits.
ComplexityO(n) iterations time, O(1) space — n−2 iterations, each a constant number of big-integer ops → O(n) iterations. Only two terms retained → O(1) variables (though each holds a huge number).
E · Edge cases and pitfalls7t₁=0, t₂=1, n=5 — Loop produces 1,2,5 → returns 5.Explore edge casesHide edge cases
Edge cases handled
t₁=0, t₂=1, n=5Loop produces 1,2,5 → returns 5.t₁=2, t₂=0, n=4t₃=2+0=2, t₄=0+4=4 → returns 4.n = 2Loop skipped; returns the seed t₂.t₁=2, t₂=2, n=20Grows to thousands of digits; BigInteger/Python int return the exact value.
Pitfalls
- Using long in Java — overflow within a few steps, producing wrong (often negative) values.
- Squaring prev (the older term) instead of cur.
- Off-by-one loop bounds from mishandling 1-indexing.
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) { if (n == 1) return BigInteger.valueOf(t1); if (n == 2) return BigInteger.valueOf(t2);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Overflow from fixed-width integers
Squaring doubles the digit count each step; a long overflows by the 4th–5th term and silently returns garbage.
Explore the code comparisonHide the code comparison
Overflow from fixed-width integers
Squaring doubles the digit count each step; a long overflows by the 4th–5th term and silently returns garbage.
Don't write this
long prev = t1, cur = t2;
for (int i = 3; i <= n; i++) {
long next = prev + cur * cur; // overflows fast
prev = cur; cur = next;
}Write this instead
BigInteger prev = BigInteger.valueOf(t1), cur = BigInteger.valueOf(t2);
for (int i = 3; i <= n; i++) {
BigInteger next = prev.add(cur.multiply(cur));
prev = cur; cur = next;
}2Squaring the wrong term
The recurrence adds the older term and squares the newer term. Squaring t(i-2) yields a completely different sequence.
Explore the code comparisonHide the code comparison
Squaring the wrong term
The recurrence adds the older term and squares the newer term. Squaring t(i-2) yields a completely different sequence.
Don't write this
prev, cur = cur, prev * prev + cur # squared the older termWrite this instead
prev, cur = cur, prev + cur * cur # square the newer term3Off-by-one indexing
The seeds are t₁ and t₂ (1-indexed). Looping from i=2 or to n-1 returns the wrong term.
Explore the code comparisonHide the code comparison
Off-by-one indexing
The seeds are t₁ and t₂ (1-indexed). Looping from i=2 or to n-1 returns the wrong term.
Don't write this
for _ in range(2, n): # too few iterations
...Write this instead
for _ in range(3, n + 1):
...Revise
Carry the pattern into the interview
Pattern to remember
Forward iteration of a nonlinear recurrence with arbitrary-precision arithmetic
Code pattern to memorize
prev, cur = t1, t2 # t1, t2 are the first two terms
for i in 3..n:
prev, cur = cur, prev + cur*cur # t(i) = t(i-2) + t(i-1)^2
return curRules to remember
- 1The recurrence is nonlinear: the later term is squared. That single square is why the numbers explode and why the term index matters so much.
- 2Each new term uses
t(i-2) + t(i-1)²— the older term is added, the newer term is squared. Don't swap them. - 3Values overflow 64-bit almost immediately. In Java use `BigInteger`; in Python the built-in
intis already arbitrary precision. - 4Keep only the last two terms — the recurrence reaches back exactly two steps, so two variables suffice.
- 5The sequence is 1-indexed in the statement: t₁ and t₂ are the seeds, and you want tₙ — set the loop to run from index 3 to n.
Use this pattern when
- A recurrence where terms grow faster than any fixed-width integer can hold
- Exact big-number results required (no modulus, no floating point)
- Nonlinear sequence recurrences (squares, products) with a small number of terms
- Any 'compute the nth term' problem where overflow is the real challenge
Choose another pattern when
- Answer is requested modulo a prime → reduce each step; BigInteger not needed
- Recurrence is linear and n is huge → matrix exponentiation in O(log n)
- Floating-point approximation acceptable → use doubles, skip big integers
- Terms stay small/bounded → plain long suffices
Interview takeaway
When a recurrence squares its terms, magnitude — not algorithmic complexity — is the hard part. The loop is trivially O(n); the real skill is recognising you need arbitrary-precision integers and reaching for BigInteger (Java) while leaning on Python's native bignums.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternForward iteration of a nonlinear recurrence where the dominant difficulty is numeric magnitude, not algorithmic complexity. Two rolling variables suffice; the engineering decision is arbitrary-precision arithmetic (BigInteger in Java, native int in Python). Recognise 'squared/multiplied terms, exact result, no modulus' as the big-integer signal.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Climbing StairsLinear Fibonacci — the same two-variable roll, but values stay small (no squaring).
- Red John is BackAnother recurrence-driven count, here feeding a sieve instead of squaring.
- Construct the ArrayA counting recurrence where a modulus replaces big integers.
- Pow(x, n) / Fast ExponentiationComing soonWhen a linear recurrence has huge n, matrix exponentiation gives O(log n) — contrast with this nonlinear case.