Coding problem · Easy · Basics

Fibonacci Number

Easy Algorithms & data structures

The Fibonacci sequence starts 0, 1, and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, .... Return the nth number (F(0) = 0). 0 <= n <= 45.

Example 1

Input: n = 6
Output: 8

Example 2

Input: n = 1
Output: 1

Hints

Hint 1

Keep just the last two numbers and update them n times.

Hint 2

The plain recursive version recomputes the same values exponentially many times: try n = 40 with it!

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Iterate with two variables (a, b) = (b, a + b). That's O(n) time and O(1) space, versus O(2ⁿ) for naive recursion.

Reference solution

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

function fib(n: number): number {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

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

<?php

function fib(int $n): int
{
    [$a, $b] = [0, 1];
    for ($i = 0; $i < $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $a;
}

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

Was this page helpful?