Problem statement

The Fibonacci numbers form the sequence F where each number is the sum of the two before it, starting from 0 and 1:

F(0) = 0,  F(1) = 1
F(n) = F(n - 1) + F(n - 2)   for n > 1

Given n, calculate F(n).

Example 1

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

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

Example 3

Input: n = 0
Output: 0

Constraints

• 0 <= n <= 46
• The answer fits in a signed 32-bit integer.

Follow-up: The naive recursion is O(2^n). Can you answer in O(n) time and O(1) space?

Hints for Fibonacci Number

1. Hint 1

   Plain recursion recomputes the same F(k) exponentially many times.

2. Hint 2

   Only the last two values ever matter, so carry them in two variables and slide forward.

3. Hint 3

   Start with a = F(0) = 0 and b = F(1) = 1, then repeat (a, b) = (b, a + b) exactly n times.

How to solve Fibonacci Number

Only the last two Fibonacci values matter for the next, so keep them in two variables and slide the pair forward n times.

Approach

1. Start a = F(0) = 0, b = F(1) = 1.
2. Repeat n times: (a, b) = (b, a + b).
3. Return a.

Why it works

After k iterations the pair holds (F(k), F(k+1)) — true at k = 0, and each step advances it by the recurrence. Naive recursion recomputes the same subproblems exponentially many times; the sliding pair is the bottom-up DP with its table compressed to two cells.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Returning b instead of a gives F(n+1).
• Memoised recursion is also linear but risks stack depth for large n.

Reference solution

Python

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Java

public static int fib(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return a;
}

C++

int fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return (int) a;
}

JavaScript

var fib = function(n) {
    let a = 0, b = 1;
    for (let i = 0; i < n; i++) {
        const next = a + b;
        a = b;
        b = next;
    }
    return a;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy