EasyMathDynamic ProgrammingRecursionMemoizationUpdated Sep 2026

509. Fibonacci Number

Asked at Meta

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Math

Companies

1

Problem

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1. After that, every number is the sum of the two numbers before it: F(n) = F(n-1) + F(n-2).

You are given an integer n. Return the value of F(n).

For example, F(2) = F(1) + F(0) = 1, and F(3) = F(2) + F(1) = 2. The answer must be the exact number, not a count or an index.

Each number is the sum of the two before it

F5 + 8 = 1301123580123456F(5) = 5 and F(6) = 8, so F(7) would be 13
The sequence grows from 0 and 1; every later value is the sum of its two left neighbours.

Constraints

  • ●0 <= n <= 30

Examples

Example 1
Inputn = 2
Output1
WhyF(2) is the sum of the two previous values: F(1) + F(0) = 1 + 0 = 1.
Example 2
Inputn = 3
Output2
WhyF(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3
Inputn = 4
Output3
WhyF(4) = F(3) + F(2) = 2 + 1 = 3.

Asked At

1 companies
CompanyDifficulty
MetaEasyView all Meta questions →

How to Think About It

1

Brute force recursive: fib(n) = fib(n-1) + fib(n-2) with base cases F(0)=0, F(1)=1. Time is O(2^n) due to repeated subproblems.

2

Memoization: store computed values in a HashMap or array to avoid recomputation. Time becomes O(n), space is O(n).

3

Bottom-up DP: iterate from 0 to n, storing only the last two values. Time is O(n), space is O(1).

4

The iterative approach with two variables a and b is the most space-efficient. At each step, compute c = a + b, then shift: a = b, b = c.

5

Matrix exponentiation can solve it in O(log n) time using the identity [[1,1],[1,0]]^n, but the iterative approach is sufficient for interviews.

6

Example: fib(6). Steps: a=0,b=1 -> c=1 -> a=1,b=1 -> c=2 -> a=1,b=2 -> c=3 -> a=2,b=3 -> c=5 -> a=3,b=5 -> c=8. Answer is 8.

Optimal Approach

Step 1: Handle base cases: if n <= 1, return n.

Step 2: Initialize two variables: a = 0 (F(0)), b = 1 (F(1)).

Step 3: Loop from 2 to n (inclusive). In each iteration, compute c = a + b, then update a = b, b = c.

Step 4: After the loop, return b (which holds F(n)).

Step 5: Example walkthrough for n = 6:
Start: a=0, b=1
i=2: c=0+1=1, a=1, b=1
i=3: c=1+1=2, a=1, b=2
i=4: c=1+2=3, a=2, b=3
i=5: c=2+3=5, a=3, b=5
i=6: c=3+5=8, a=5, b=8
Return 8.

Time: O(n). Space: O(1).

Rolling two variables forward

a = 0, b = 1c = a + ba = b, b = crepeat until i = nStart with F(0) and F(1), then advance one index perloop passn = 6icabstep23456icab21113212432355356858After the last pass b holds F(6) = 8, which is theanswerif n <= 1: return na, b = 0, 1a, b = b, a + breturn b
Keep only the last two values, a and b. Each step makes a new c = a + b, then shifts the pair.
ComplexityTime O(n)Space O(1)The loop runs n-1 times and only two variables are kept, so the cost is linear time and constant extra space.

What Trips People Up in Real Interviews

1

Writing the naive recursive solution without memoization. It has O(2^n) time and will timeout for n > 35.

2

Using a full DP array when only two variables are needed. This wastes space unnecessarily.

3

Off-by-one errors in the loop bounds. Make sure to iterate exactly n-1 times for the two-variable approach.

4

Forgetting the base cases F(0) = 0 and F(1) = 1. Always clarify the base cases with the interviewer.

5

Trying to use the closed-form Binet formula with floating point. It loses precision for n > 70 due to floating point limitations.

Solution Code

O(n) time
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Fibonacci Number problem?

Given n, calculate the nth Fibonacci number where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

How do you solve Fibonacci Number?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Fibonacci Number?

Fibonacci Number is asked at Meta. It is a easy difficulty problem.

What are common mistakes on Fibonacci Number?
  • Writing the naive recursive solution without memoization. It has `O(2^n)` time and will timeout for n > 35.
  • Using a full DP array when only two variables are needed. This wastes space unnecessarily.
  • Off-by-one errors in the loop bounds. Make sure to iterate exactly n-1 times for the two-variable approach.
  • Forgetting the base cases F(0) = 0 and F(1) = 1. Always clarify the base cases with the interviewer.
  • Trying to use the closed-form Binet formula with floating point. It loses precision for n > 70 due to floating point limitations.