Fibonacci Number

Solved

Difficulty: Basic Accuracy: — Submissions: 0 Points: 1

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1, and every later term is the sum of the two before it. Given n, return F(n).

Examples:

Input: n = 2

Output: 1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 10

Output: 55

Explanation: The sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Constraints:

0 ≤ n ≤ 60

Expected Complexities

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

Company Tags

Amazon

Topic Tags

Basic Math

The recursive definition is the obvious first attempt, but it recomputes the same values again and again and becomes unusable around n = 40. Keep the last two terms in two variables and step forward n times instead: linear time, constant space. Use a 64-bit type because F(60) is larger than 2^31.

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