DEV Community

loading...
Cover image for Solution: Fibonacci Number

Solution: Fibonacci Number

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・3 min read

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:

Binet's Formula

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
};
Enter fullscreen mode Exit fullscreen mode
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
};
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode
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
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode
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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)