Solution: Fibonacci Number
Tags: algorithms, javascript, java, python
Published: 2021-04-15 08:13:58

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/fibonacci-number/discuss/1159381).*

---

#### [Leetcode Problem #509 (*Easy*): Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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](https://wikimedia.org/api/rest_v1/media/math/render/svg/57459135cb5773799fab490a49311b3725df94fd)

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Binet's formula:***
```javascript
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:***
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Binet's formula:***
```python
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:***
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Binet's formula:***
```java
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:***
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ Binet's formula:***
```c++
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:***
```c++
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;
    }
};
```