# Fibonacci Number LeetCode Solution

Difficulty Level Easy
ZoomViews 3576

## Problem Statement

Fibonacci Number LeetCode Solution – “Fibonacci Number” states that 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)`.

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

## Approach

### Idea:

The main observation is that each F(i) is depending on the sum of F(i-1) and F(i-2). Thus we can take two variables that will store the initial value, then we will iterate till N to get the result.

### explanation

• N==0: return 0
• N==1: return 1
• default: return fib(N-1) + fib(N-2)

let’s talk about the second approach:

Considering the sequence of [34,55,89] we can see a pattern that is if we divide any two consecutive terms, the division results in an identical number close to 1.618 called the golden ratio. Indeed we have the formula to do this! called Binet’s formula.

Okay? how can we use this golden something! 34 is the 9th term, If we find the `pow(golden,Nth term)/sqrt(5)` enclosed with a round function, we would get the Nth term value in O(1) time & space!

## Code

### C++ Code of Fibonacci Number

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

}
};```

### JAVA Program of Fibonacci Number

```class Solution {
public int fib(int n) {
if(n==0)
return 0;
if (n==1)
return 1;
int a=0,b=1,c=0;

for(int i=1;i<n;i++)
{
c=a+b;
a=b;
b=c;
}
return c;

}
}```

O(N)

O(1)

Translate »