1.2) Fibonacci Number

The Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Given an integer n, find the n-th Fibonacci number.

Sample Input/Output:

Let’s consider a sample input:

n = 6

Expected Output:

8

Explanation:
For the given input n = 6, the Fibonacci sequence is [0, 1, 1, 2, 3, 5, 8]. The 6th Fibonacci number is 8.

Time and Space Complexity:

The time complexity of the solution will be O(n), where n is the input integer. This is because we calculate each Fibonacci number once and store it in an array.

The space complexity will be O(n) to store the array of Fibonacci numbers.

Fibonacci Number C++ Solution:

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }

    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n = 6;

    int result = fibonacci(n);

    cout << "The " << n << "-th Fibonacci number is: " << result << endl;

    return 0;
}

In this implementation, we use dynamic programming to calculate the n-th Fibonacci number. We create an array fib to store the Fibonacci numbers from 0 to n. We start by initializing the first two Fibonacci numbers (0 and 1) and then iteratively calculate the remaining Fibonacci numbers using the formula fib[i] = fib[i – 1] + fib[i – 2].

The main function demonstrates the usage of the fibonacci function by calculating the n-th Fibonacci number.

The output for the provided test case will be:

The 6-th Fibonacci number is: 8