easy

Fibonacci Number

Compute the nth number in the Fibonacci sequence.

1. Define the problem

Fibonacci Number

The Fibonacci numbers form a sequence where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Given n, return F(n). Plain recursion recomputes F(2) an exponential number of times because the same subproblem is asked for over and over. Build the answer bottom-up from F(0) and F(1), reusing each earlier value exactly once.

Constraints

  • 0 ≤ n ≤ 30

Example

Inputn = 5
Output5

Explanation F(5) = F(4) + F(3) = 3 + 2 = 5.

2. Visualize the solution

Build the Fibonacci table from F(0) up to F(n)

Build the Fibonacci table from F(0) up to F(n)
Statusbase

The whole table for n = 5 is laid out. F(0) = 0 and F(1) = 1 are the base cases; the rest are still blank.

What happens in this step

F(0) = 0
F(1) = 1

These are given directly by the problem, not computed. F(2) to F(5) are still blank — every one of them will be built from these two.
Step 1 of 5

Steps to visualize

  1. Set the base cases: F(0) = 0 and F(1) = 1.
  2. For every i from 2 to n, set F(i) = F(i-1) + F(i-2).
  3. Each new value reuses the two cells directly before it.
  4. The value at F(n) is the answer.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Build the Fibonacci table from F(0) up to F(n)
Statusbase

The whole table for n = 5 is laid out. F(0) = 0 and F(1) = 1 are the base cases; the rest are still blank.

What happens in this step

F(0) = 0
F(1) = 1

These are given directly by the problem, not computed. F(2) to F(5) are still blank — every one of them will be built from these two.
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  let prev2 = 0;
  let prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
n = 55example from the docstring
n = 00smallest valid input, base case F(0)
n = 11base case F(1)
n = 21first value built from both base cases
n = 43a few steps of accumulation
n = 1055a longer run of accumulation
n = 30832040upper bound of the constraint range

Keep reading