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

*Description:*

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

The

Fibonacci numbers, commonly denoted`F(n)`

form a sequence, called theFibonacci 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:*

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

*Constraints:*

- 0 <= n <= 30

####

*Idea:*

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

*Implementation:*

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

####

*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####

*w/ Binet’s formula:*

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

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

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####

*w/ Binet’s formula:*

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

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

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####

*w/ Binet’s formula:*

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

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

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####

*w/ Binet’s formula:*

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

*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;
}
};
```