Problem Statement

Given an integer N, find the Nth Fibonacci number.

Examples

Example 1:

Input: n = 3

Output: 1

Explanation: The Fibonacci series is as follows:

Fib(0) = 0

Fib(1) = 1

Fib(2) = Fib(0) + Fib(1)

Fib(n) = Fib(n-1) + Fib(n-2)

0 + 1 + 1 + 2….

Therefore the 3rd Fibonacci number is 1.

Theory

Recursive Solution

The simplest way to find the Nth Fibonacci number is by using recursion. The recursive formula for the Fibonacci sequence is:

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

where F(0) = 0 and F(1) = 1.

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

Although this recursive solution is simple, it has exponential time complexity O(2^N), making it impractical for large values of N.

Different Approaches

1 Memoization Approach (Top-Down)

Memoization involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.

#include <iostream>
#include <vector>

std::vector<long long> memo;

long long fibonacci(int n) {
    if (memo[n] != -1)
        return memo[n];
    if (n <= 1)
        return n;
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n = 50;
    memo.resize(n + 1, -1);
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Complexity Analysis

• Time Complexity:O(n)
• Space Complexity:O(n)

2 Tabulation Approach (Bottom-Up)

Tabulation involves solving the problem by building a table iteratively.

#include <iostream>
#include <vector>

long long fibonacci(int n) {
    std::vector<long long> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    int n = 50;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}