# N-th Fibonacci Number

Back to home
Logicmojo - Updated Dec 12, 2023

## Problem Statement: N-th Fibonacci Number

Write a program to calculate the nth Fibonacci number where n is a given positive number.

Every number after the first two is the sum of the two preceding ones, which is known as Fibonacci's sequence.For example, consider the following series:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … and so on.

Given a number n, print n-th Fibonacci Number.

Examples:

Input : n = 5
Output : 5

Input : n = 10
Output : 55

We have presented two approaches to find the n-th fibonacci number:

• Using Recursion
• Using Dynamic Programming
• Using Formula

### Approach 1: Using Recursion

The following recurrence relation defines the sequence Fn of Fibonacci numbers:

F{n} = F{n-1} + F{n-2} with base values F(0) = 0 and F(1) = 1.

C++ Implementation:

```#include<bits/stdc++.h>
using namespace std;

int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}

int main ()
{
int n = 10;
cout << fib(n);
getchar();
return 0;
}

Try it Yourself

```

Java Implementation:

```class fibonacci
{
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}

public static void main (String args[])
{
int n = 10;
System.out.println(fib(n));
}
}

Try it Yourself

```

Python Implementation:

```def fibonacci(n, second_last, last):
if n-1 == 0:
return second_last
else:
new_last = second_last + last
second_last = last
return fibonacci(n-1, second_last, new_last)

if __name__ == "__main__":
print(fibonacci(10, 0, 1))

Try it Yourself

```

Time complexity: O(n), which is a linear

Space complexity:O(n) if we consider the function call stack size, otherwise O(1).

### Approach 2: Using Dynamic Programming

We can also improve the time complexity of the recursive approach by saving values that have already been calculated in a data structure like a list. And the function fib() will check if a subproblem is already solved or not. If solved before we will not solve it again.

C++ Implementation:

```#include <iostream>
#include <unordered_map>
using namespace std;

int fib(int n, auto &lookup)
{
if (n <= 1) {
return n;
}

if (lookup.find(n) == lookup.end()) {
lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup);
}

return lookup[n];
}

int main()
{
int n = 8;
unordered_map<int, int> lookup;

cout << "F(n) = " << fib(n, lookup);

return 0;
}

Try it Yourself

```

Java Implementation:

```import java.util.HashMap;
import java.util.Map;

class Main
{
public static int fib(int n, Map<Integer, Integer> lookup)
{
if (n <= 1) {
return n;
}

lookup.putIfAbsent(n, fib(n - 1, lookup) + fib(n - 2, lookup));

return lookup.get(n);
}

public static void main(String[] args)
{
int n = 10;
Map<Integer, Integer> lookup = new HashMap<>();

System.out.println("F(n) = " + fib(n, lookup));
}
}

Try it Yourself

```

Python Implementation:

```def fib(n, lookup):

if n <= 1:
return n

if n not in lookup:
lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup)

return lookup[n]

if __name__ == '__main__':

n = 8
lookup = {}

print('F(n) =', fib(n, lookup))

Try it Yourself

```

### Approach 3: Using Formula

In this method we directly implement the formula for nth term in the fibonacci series.

Fn = {[(√5 + 1)/2] ^ n} / √5

C++ Implementation:

```#include<iostream>
#include<cmath>

int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}

int main ()
{
int n = 10;
std::cout << fib(n) << std::endl;
return 0;
}

Try it Yourself

```

Java Implementation:

```import java.util.*;

class Main{

static int fib(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n)/ Math.sqrt(5));
}

public static void main(String[] args) {
int n = 9;
System.out.println(fib(n));
}
}

Try it Yourself

```

Python Implementation:

```import math

def fibo(n):
phi = (1 + math.sqrt(5)) / 2

return round(pow(phi, n) / math.sqrt(5))

if __name__ == '__main__':

n = 10

print(fibo(n))

Try it Yourself

```

Time Complexity: O(logn), this is because calculating phi^n takes logn time

Space Complexity: O(1)

With this article at Logicmojo, you must have the complete idea of solving Nth Fibonacci Number problem.