Skip to main content

509. Fibonacci Number

easyAsked at Intel

Compute the nth Fibonacci number. Intel asks because the question has FOUR escalating optimal solutions (naive recursion → memoization → iterative → matrix exponentiation), and the interviewer is grading how far up the ladder you can climb. Reaching matrix exponentiation lands the senior numerical-software signal.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports list Fibonacci as a recurring DP-ladder warm-up.
  • GeeksforGeeks (2025-08)— Intel Interview Experience archives reference Fibonacci with the matrix-exponentiation follow-up.
  • LeetCode discuss (2025-12)— Intel-tagged in the LC company-frequency filter.

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

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

Example 3

Input
n = 4
Output
3

Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Approaches

1. Naive recursion (brute)

Translate the recurrence literally. fib(n) = fib(n-1) + fib(n-2).

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

Tradeoff: Exponential — recomputes the same subproblems. Showing this first is fine for the narration; never the final answer.

2. Iterative (optimal — most common ship)

Track only the last two values. Walk up from F(0) and F(1).

Time
O(n)
Space
O(1)
function fib(n) {
  if (n < 2) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

Tradeoff: Linear time, constant space, no recursion overhead. The right answer for any n up to ~10^7. Beyond that you start wanting matrix exponentiation.

3. Matrix exponentiation (optimal — log time)

F(n) is the top-right entry of [[1,1],[1,0]]^n. Use fast exponentiation on the 2x2 matrix.

Time
O(log n)
Space
O(1)
function fibMatrix(n) {
  if (n < 2) return n;
  // Multiply two 2x2 matrices A and B in-place into A.
  function mul(A, B) {
    return [
      A[0] * B[0] + A[1] * B[2], A[0] * B[1] + A[1] * B[3],
      A[2] * B[0] + A[3] * B[2], A[2] * B[1] + A[3] * B[3],
    ];
  }
  let result = [1, 0, 0, 1]; // identity
  let base = [1, 1, 1, 0];
  while (n > 0) {
    if (n & 1) result = mul(result, base);
    base = mul(base, base);
    n = Math.floor(n / 2);
  }
  // F(n) sits in result[1]
  return result[1];
}

Tradeoff: Logarithmic in n. Same fast-exponentiation skeleton as Pow(x, n), applied to a 2x2 matrix. Overkill for n <= 30 but the canonical 'do better than linear' answer Intel fishes for.

Intel-specific tips

Intel's escalation pattern on this problem is consistent: candidate writes naive recursion, interviewer asks 'can you do better?' twice. The first 'better' gets you iterative; the second 'can you do better than linear?' is the matrix exponentiation lever. Mention that matrix exponentiation generalizes to ANY linear recurrence — that's the Intel-flavored math insight that lands.

Common mistakes

  • Memoized recursion stored on a global object — works but unnecessary; iterative gets the same Big-O with simpler code.
  • Off-by-one in the iterative loop: starting prev=1, curr=1 instead of prev=0, curr=1 gives F(1)=1, F(2)=2 — wrong shift.
  • Matrix exponentiation with a fresh array allocation every step — quadratic memory churn; use the in-place pattern.

Follow-up questions

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

  • Climbing Stairs (LC 70) — same recurrence, +1 offset on the index.
  • Tribonacci (LC 1137) — three-term linear recurrence; matrix becomes 3x3.
  • How does Binet's formula (closed-form Fibonacci) compare in practice? (Constant-time on paper, but floating-point precision breaks for n > 70 or so.)

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 does the 2x2 matrix work for Fibonacci?

[[1,1],[1,0]] applied to vector [F(n), F(n-1)] produces [F(n)+F(n-1), F(n)] = [F(n+1), F(n)]. So multiplying that matrix n times against [1, 0] = [F(1), F(0)] yields [F(n+1), F(n)].

Is the closed-form (golden ratio) solution useful in practice?

Theoretically O(1) using Binet's formula F(n) = (phi^n - psi^n) / sqrt(5). In practice, double-precision rounding makes it incorrect past n ≈ 70. Matrix exponentiation is the right 'constant in log-time' answer for arbitrary precision.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →