Skip to main content

509. Fibonacci Number

easyAsked at JPMorgan

Compute the n-th Fibonacci number where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). JPMorgan asks this on early-career and intern phone screens to test whether you can recognise the recurrence and pivot from naive recursion to O(n) iteration in under a minute.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— JPMorgan early-career and intern phone-screen reports cite Fibonacci as the standard DP warm-up.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-10)— JPMC intern write-up: 'asked Fibonacci, then asked the O(log n) follow-up'.

Problem

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n).

Constraints

  • 0 <= n <= 30

Examples

Example 1

Input
n = 2
Output
1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

Input
n = 3
Output
2

Example 3

Input
n = 4
Output
3

Approaches

1. Naive recursion (exponential — for understanding)

fib(n) = fib(n-1) + fib(n-2) directly. Recomputes the same subproblems exponentially many times.

Time
O(2^n)
Space
O(n) recursion
function fibRec(n) {
  if (n < 2) return n;
  return fibRec(n - 1) + fibRec(n - 2);
}

Tradeoff: Trivially correct, asymptotically catastrophic. Useful only as the baseline you optimise away from on a phone screen.

2. Memoised recursion

Recursion with a cache so each subproblem is solved at most once.

Time
O(n)
Space
O(n)
function fibMemo(n) {
  const cache = new Array(n + 1);
  function go(k) {
    if (k < 2) return k;
    if (cache[k] !== undefined) return cache[k];
    cache[k] = go(k - 1) + go(k - 2);
    return cache[k];
  }
  return go(n);
}

Tradeoff: O(n) time but still O(n) stack + cache. Easy translation from the recursive version; mention it but prefer the iterative.

3. Bottom-up DP with O(1) rolling state (optimal for n <= 30)

Track only the last two values. Compute fib(i) = prev1 + prev2 iteratively.

Time
O(n)
Space
O(1)
function fib(n) {
  if (n < 2) return n;
  let prev2 = 0;
  let prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space — the answer JPMorgan interviewers want as the primary. Mention the matrix-exponentiation O(log n) version only on the follow-up.

4. Matrix exponentiation (O(log n))

Fibonacci is the (1,1) entry of [[1,1],[1,0]]^n. Compute the matrix power in O(log n) via repeated squaring.

Time
O(log n) (assuming O(1) bigint mul)
Space
O(log n) recursion or O(1) iterative
function fibMatrix(n) {
  function mul(a, b) {
    return [
      [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
      [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
    ];
  }
  function pow(m, p) {
    let result = [[1, 0], [0, 1]];
    while (p > 0) {
      if (p & 1) result = mul(result, m);
      m = mul(m, m);
      p >>= 1;
    }
    return result;
  }
  if (n === 0) return 0;
  return pow([[1, 1], [1, 0]], n)[0][1];
}

Tradeoff: Overkill for n <= 30 but the canonical answer when n is huge (n = 10^9). JPMorgan interviewers ask for this only as the follow-up; lead with the iterative version.

JPMorgan-specific tips

JPMorgan early-career interviewers want to see the explicit progression: recursive (state the cost), memoised (improve), iterative (remove the cache), and matrix (asymptotic best). You do not need to write all four — articulating the climb scores higher than producing only the best answer cold. Time it: 30 seconds of narration before any keystrokes.

Common mistakes

  • Initialising prev2 = 1, prev1 = 1 (off-by-one — F(0)=0, F(1)=1).
  • Off-by-one on the loop bound: i = 2; i <= n; not i < n.
  • Forgetting that n=0 must return 0 — the loop never executes and prev1 stays at 1.
  • Using BigInt unnecessarily for n <= 30 — values fit in a 32-bit integer.

Follow-up questions

An interviewer at JPMorgan may pivot to one of these next:

  • Climbing Stairs (LC 70) — same recurrence, different base case.
  • Tribonacci (LC 1137) — three-term recurrence, three-variable rolling.
  • Compute Fibonacci modulo p (Pisano period).
  • Compute the n-th Fibonacci for n = 10^9 in O(log n).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the iterative version asymptotically the same as memoised recursion but practically better?

Both are O(n) time, but memoised recursion uses O(n) stack and O(n) cache; iterative uses O(1) extra. Removing the call-stack overhead also makes the iterative version faster in practice by a small constant — and avoids stack-overflow risk for large n on hosts with shallow stacks.

When would you reach for matrix exponentiation?

When n is large enough that O(n) is unacceptable — typically n >= 10^7 or when you need modular Fibonacci for cryptographic-style problems. For the LC 509 constraint (n <= 30) it is overkill, but mention it as the natural follow-up.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Fibonacci Number and other JPMorgan interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →