Solution: Fibonacci Number

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #509 (Easy): Fibonacci Number

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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).

---

Examples:

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

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

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

---

Constraints:

• 0 <= n <= 30

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The naive idea here would be to create an array of Fibonacci numbers by doing as the directions indicate: adding the two previous numbers together to find the next number.

But we can find the answer here in O(1) space by instead just keeping track of only the previous two numbers (a, b) and rolling over the variable contents in a circular pattern.

Since our rolling loop can only begin on the third number or later, we'll first have to deal with the early n-value edge cases with a special return statement.

Update: Apparently there's a mathematical formula for Fibonacci numbers: Binet's formula.

Binet's formula for the n'th Fibonacci number:

This formula can compute the solution in O(1) time as well as O(1) space.

---

Implementation:

There are only minor differences betwen the code of all four languages.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

w/ Binet's formula:

var fib = function(n) {
    let sqrt5 = Math.sqrt(5)
    return (Math.pow(1 + sqrt5, n) - Math.pow(1 - sqrt5, n)) / Math.pow(2, n) / sqrt5
};

w/ O(N) iteration:

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

---

Python Code:

(Jump to: Problem Description || Solution Idea)

w/ Binet's formula:

class Solution:
    def fib(self, n: int) -> int:
        sqrt5 = sqrt(5)
        return int((pow(1 + sqrt5, n) - pow(1 - sqrt5, n)) / pow(2, n) / sqrt5)

w/ O(N) iteration:

class Solution:
    def fib(self, n: int) -> int:
        if n < 2: return n
        a, b = 0, 1
        for _ in range(1,n):
            a, b = b, a+b
        return b

---

Java Code:

(Jump to: Problem Description || Solution Idea)

w/ Binet's formula:

class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        return (int)((Math.pow(1 + sqrt5, n) - Math.pow(1 - sqrt5, n)) / (double)Math.pow(2, n) / sqrt5);
    }
}

w/ O(N) iteration:

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

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

w/ Binet's formula:

class Solution {
public:
    int fib(int n) {
        double sqrt5 = sqrt(5);
        return (pow(1 + sqrt5, n) - pow(1 - sqrt5, n)) / pow(2, n) / sqrt5;
    }
};

w/ O(N) iteration:

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