Skip to main content

Math Basics

Fibonacci Number Solution in C++/Java/Python/JS

A Fibonacci number is part of a sequence of numbers known as the Fibonacci sequence, which is characterized by the fact that every number after the first two is the sum of the two preceding ones. The sequence starts with 0 and 1, and from there, each subsequent number is the sum of the previous two:

Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Given an integer n, find the nth Fibonacci number.

Examples : 

Input: 1
Output: 1
Explanation: 0 is considered as the zeroth Fibonacci number, and 1 is considered as the first Fibonacci number.

Input: 6
Output: 8
Explanation: The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8. So the 6th Fibonacci number is 8.

We know the Fibonacci number is a sequence of numbers where the current number is the sum of the last 2 succeeding numbers.

Initially, the first 2 numbers in the sequence are 0 and 1.

So let's use an array to store the Fibonacci number where f[0] = 0 is the zeroth element and f[1] = 1 first element. Now for each i (2 to n) f[i] = f[i-1] + f[i-2].

So the answer f[n] will store the nth Fibonacci number of the sequence.

Now Can we optimize this, so that we can find the nth Fibonacci number without using an array?

If we look closely to find the current element we only need the last two elements i.e. (for an ith number we need i-1 and i-2 numbers).

So we can avoid using an array and instead of it we could use 2 variables prev1(for the i-1th index) and prev2(for the i-2th index).

Now for every ith index from 2 to n, the current element(cur) is equal to the previous Fibonacci Number(i-1th index i.e. prev1) + previous of previous Fibonacci Number(i-2th index i.e. prev2).

So in general our cur = prev1 + prev2.

Now for the next iteration, we update our prev1 to cur and prev2 to prev1 i.e. preparing our variables to find the Fibonacci sequence for the i+1 index.

Code Implementation
C++ Code Try on Compiler! 
// Function to calculate the nth Fibonacci number
int fibonacci(int n) {
    // If n is 0 or 1, return n as the Fibonacci number at these positions is the same as n
    if (n <= 1) {
        return n;
    }

    // Initialize the first two Fibonacci numbers
    // F(0) = 0
    int prev1 = 0; 
    // F(1) = 1
    int prev2 = 1; 

    // Iterate from the 2nd position to the nth position
    for (int i = 2; i <= n; i++) {
        // Calculate the next Fibonacci number
        int cur = prev1 + prev2;

        // Update prev and curr to the next pair of Fibonacci numbers
        prev1 = cur;
        prev2 = prev1;
    }

    // Return the nth Fibonacci number
    return prev1;
}

Java Code Try on Compiler! 
public class Fibonacci {
    public static int fibonacci(int n) {
        // If n is 0 or 1, return n as the Fibonacci number
        if (n <= 1) {
            return n;
        }

        // Initialize the first two Fibonacci numbers
        int prev1 = 0; // F(0) = 0
        int prev2 = 1; // F(1) = 1

        // Iterate from the 2nd position to the nth position
        for (int i = 2; i <= n; i++) {
            // Calculate the next Fibonacci number
            int cur = prev1 + prev2;

            // Update prev1 and prev2
            prev1 = cur;
            prev2 = prev1;
        }

        // Return the nth Fibonacci number
        return prev1;
    }
}

Python Code Try on Compiler! 
def fibonacci(n):
    # If n is 0 or 1, return n as the Fibonacci number
    if n <= 1:
        return n

    # Initialize the first two Fibonacci numbers
    prev1 = 0  # F(0) = 0
    prev2 = 1  # F(1) = 1

    # Iterate from the 2nd position to the nth position
    for _ in range(2, n + 1):
        # Calculate the next Fibonacci number
        cur = prev1 + prev2

        # Update prev1 and prev2
        prev1 = cur
        prev2 = prev1

    # Return the nth Fibonacci number
    return prev1

Javascript Code Try on Compiler! 
// Function to calculate the nth Fibonacci number
function fibonacci(n) {
    // If n is 0 or 1, return n as the Fibonacci number
    if (n <= 1) {
        return n;
    }

    // Initialize the first two Fibonacci numbers
    let prev1 = 0; // F(0) = 0
    let prev2 = 1; // F(1) = 1

    // Iterate from the 2nd position to the nth position
    for (let i = 2; i <= n; i++) {
        // Calculate the next Fibonacci number
        let cur = prev1 + prev2;

        // Update prev1 and prev2
        prev1 = cur;
        prev2 = prev1;
    }

    // Return the nth Fibonacci number
    return prev1;
}

Time Complexity

The time complexity of computing the Fibonacci of n is O(n). This is because the algorithm involves a single loop that iterates from 1 to n. A constant-time operation (addition and assignment) is performed in each iteration. Thus, the total time complexity is proportional to the number of iterations, n.

Space Complexity

The space complexity of this algorithm is O(1). The algorithm uses a fixed amount of extra space regardless of the input size. It only requires a few variables (like the result and the loop counter), and the amount of memory needed does not grow with n.