Practice the most popular front-end questions asked in coding interviews with Frontend Churn

00:00:00

Given an integer n, return the nth Fibonacci number.

In mathematics, the Fibonacci numbers, form a sequence called the Fibonacci sequence - In which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1.

To get an nth fibonacci number, you can use the following equation

```
F(n) = F(n-1) + F(n-2)
```

```
n = 10
```

```
Output: 34
```

- The
`nth`

fibonacci, in this case, the 10th fibonacci number is calculated as follows. `first`

=`0`

(According to the definition)`Second`

=`1`

(According to the definition)`Third`

=`first + second`

=`1 + 0`

=`1`

`Fourth`

=`Third + Second`

=`1 + 1`

=`2`

`Fifth`

=`Fourth + Third`

=`2 + 1`

=`3`

`Sixth`

=`Fifth + Fourth`

=`3 + 2`

=`5`

and so on till...

`Tenth`

=`Ninth + Eighth`

=`21 + 13`

=`34`

- This is our solution.

Simple formula is: `F(n) = F(n-1) + F(n-2)`

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

```
0 <= n <= 30
```

Click to reveal

Can you try the brute force approach by using `sum`

to calculate the previous two values? A for loop would help.

Click to reveal

Can recursion help? What if you can compute the sum of the previous two values by `sum = Fibonacci(n-1) + Fibonacci(n-2)`

Click to reveal

Can you use objects / hash maps to improve the time complexity of the recursive algorithm?

Uploaded by: Manu Arora

Share this problem on