Skip to main content

509. Fibonacci Number

easy

Compute the n-th Fibonacci number. The textbook 'naive recursion is exponential, memoization is linear, two-variable iteration is constant space' progression in one tiny problem.

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

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.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive recursion: F(n) = F(n-1) + F(n-2). Exponential without memo because subproblems overlap.

Hint 2

Memoize: pass a cache; each F(k) computed once -> O(n) time, O(n) space.

Hint 3

Iterative two-variable: prev = 0, curr = 1; for i from 2 to n compute next = prev + curr; advance. O(n) time, O(1) space.

Hint 4

There's also a closed-form using the golden ratio — fast but susceptible to floating-point error.

Solution approach

Reveal approach

Three solutions in order of sophistication. (1) Naive recursion: fib(n) returns n if n < 2 else fib(n-1) + fib(n-2). Exponential — interview red flag. (2) Memoized recursion: cache results in an array or map; each subproblem computed once -> O(n) time, O(n) space. (3) Bottom-up iteration with two variables: prev, curr = 0, 1. For i from 2 to n: next = prev + curr; prev = curr; curr = next. Return n if n < 2 else curr. O(n) time, O(1) extra space. Ship version (3). Also valid: matrix exponentiation in O(log n) for very large n, plus the Binet closed-form for small n with FP caveats.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • recursion
  • memoization
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Fibonacci Number and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →