Fibonacci Number

The key idea

Each Fibonacci number depends only on the two before it. Build the answer upward from the base cases F(0)=0 and F(1)=1, reusing each result instead of recomputing it — so the work is one pass, not an exponential tree.

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

Input: n = 2 Output: 1

Input: n = 3 Output: 2

Input: n = 4 Output: 3

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →