# Find the Nth Fibonacci number | C++

Here, we are going to learn **how to find the Nth Fibonacci number using Dynamic programming in C++**.

Submitted by Ritik Aggarwal, on November 07, 2018

**Problem:** Compute the N^{th} Fibonacci number

You are given a number N. You have to **find the N ^{th} Fibonacci number**. 0

^{th}Fibonacci number is 0 and first Fibonacci number is 1.

**Sample inputs:**

N = 0, answer is 0 N = 1, answer is 1 N = 5, answer is 5

**Basic Approach: Recursive approach**

int fibonacci(int N){ if(N == 0 || N == 1){ return N; } int ans = fibonacci(N-1) + fibonacci(N - 2); return ans; }

Now provided above is the basic recursive approach which takes **O(2^N)** time to compute as every call needs to call two other calls but if we already have the answers of two other calls in an array then we can directly use them.

**Top Down Approach:**

int fibonacciTopDown(int N, int strg[]){ if(N == 1 || N == 0){ return N; } if(strg[N] != 0){ return strg[N]; } int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg); strg[N] = ans; return ans; }

Now the top down approach also uses recursion but before returning the answer to the solution we store the answer in strg array so that if we needed the answer again then we could simply use that answer directly from our array. The time complexity of the program is **O(N)**.

**Bottom Up Approach:**

int fibonacciBottomUp(int N){ int strg[N + 1] = {0}; strg[0] = 0; strg[1] = 1; for(int i = 2;i<N+1;i++){ strg[i] = strg[i-1] + strg[i-2]; } return strg[N]; }

This is the Bottom Up approach with time complexity as **O(N)**. Now we have an iterative method to the recursive problem.

As seen above from the dp approaches we can very easily see that storage matrix or dp matrix has some meaning. For example, In the Fibonacci case, the **N ^{th}** index of strg matrix stores the

**N**fibonaaci number that's why we can very easily write this line strg[i] = strg[i-1] + strg[i-2].

^{th}As stated above start solving dp problems with recursion first and then proceed to dp. Try assigning some meaning to the storage matrix or dp matrix and formulate the correct equation.

**Code to find the Nth Fibonacci number using all given approaches **

#include <iostream> using namespace std; int fibonacci(int N){ if(N == 0 || N == 1){ return N; } int ans = fibonacci(N-1) + fibonacci(N - 2); return ans; } int fibonacciTopDown(int N, int strg[]){ if(N == 1 || N == 0){ return N; } if(strg[N] != 0){ return strg[N]; } int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg); strg[N] = ans; return ans; } int fibonacciBottomUp(int N){ int strg[N + 1] = {0}; strg[0] = 0; strg[1] = 1; for(int i = 2;i<N+1;i++){ strg[i] = strg[i-1] + strg[i-2]; } return strg[N]; } int main() { int N; cin >> N; int strg[N + 1] = {0}; cout << "The answer using recursive solution is " << fibonacci(N) << endl; cout << "The answer using Bottom up aproach is " << fibonacciBottomUp(N) << endl; cout << "The answer using Top down approach is " << fibonacciTopDown(N,strg) << endl; return 0; }

**Output**

8 The answer using recursive solution is 21 The answer using Bottom up aproach is 21 The answer using Top down approach is 21

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions