Start learning free

LESSON 180 OF 409 · LOOPS - CHALLENGES

Fibonacci Number in C++ with O(n) Time Complexity and O(1) Space Complexity

Practice Read the full explanation

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate and return F(n).


Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:


As we compute each new Fibonacci number as the sum of the previous two, we will use 2 variables prev and curr to store the last two computed Fibonacci numbers at each moment of time. We should initialize prev with 0(F(0)) and curr with 1(F(1)).

There are n - 1 more numbers to be computed: F(2), F(3), ..., F(n). Let's write a for loop that iterates with a variable i through the values 2 to n. Inside this loop, we should compute the new Fibonacci number (F(i)) and update the variables prev and curr.

At the beginning of each iteration, F(i - 2) is stored in prev, F(i - 1) is stored in curr and we want to compute F(i). At the end of the iteration, we want prev to store F(i - 1) and curr to store F(i).
So we can use another variable next to store prev + curr and then we can assign curr to prev (prev = curr) and next to curr (curr = next).

After the loop finishes execution, the answer (F(n)) lies in curr.
Also, don't forget to treat the special cases n = 0 and n = 1 (when n < 2, the answer is n itself) at the beginning of the algorithm.

STEP 1 OF 6
    Ctrl + Enter to check

    C++ · LOOPS - CHALLENGES

    Fibonacci in C++, explained

    Understanding the Problem

    The core challenge of this problem is to compute the nth Fibonacci number efficiently. The Fibonacci sequence is widely used in computer science and mathematics, often appearing in problems related to dynamic programming, recursive algorithms, and number theory.

    Common pitfalls include using a naive recursive approach, which has exponential time complexity and is highly inefficient for large values of n.

    Approach

    To solve this problem efficiently, we can use an iterative approach that runs in O(n) time and uses O(1) space. This method involves maintaining two variables to store the last two Fibonacci numbers and updating them iteratively.

    Naive Solution

    A naive solution involves using recursion:

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

    However, this approach has exponential time complexity, O(2^n), and is not feasible for large n.

    Optimized Solution

    We can optimize the solution by using an iterative approach with two variables:

    int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; ++i) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

    Algorithm

    1. Initialize two variables, prev and curr, to store F(0) and F(1) respectively.

    2. Iterate from 2 to n, updating the variables to store the next Fibonacci number.

    3. Return the value of curr, which will be F(n) after the loop completes.

    Code Implementation

    #include <iostream>
using namespace std;

int fibonacci(int n) {
    // Handle base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Initialize variables to store F(0) and F(1)
    int prev = 0, curr = 1;
    
    // Iterate from 2 to n
    for (int i = 2; i <= n; ++i) {
        int next = prev + curr; // Compute the next Fibonacci number
        prev = curr; // Update prev to the last Fibonacci number
        curr = next; // Update curr to the current Fibonacci number
    }
    
    return curr; // Return the nth Fibonacci number
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Fibonacci number " << n << " is " << fibonacci(n) << endl;
    return 0;
}

    Complexity Analysis

    The time complexity of the optimized solution is O(n) because we iterate from 2 to n. The space complexity is O(1) because we use a constant amount of space to store the variables prev and curr.

    Edge Cases

    Consider the following edge cases:

    • n = 0: The output should be 0.
    • n = 1: The output should be 1.
    • Large values of n: Ensure the algorithm runs efficiently and does not cause overflow.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • n = 0: Expected output is 0.
    • n = 1: Expected output is 1.
    • n = 10: Expected output is 55.
    • n = 20: Expected output is 6765.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem and constraints thoroughly.
    • Start with a naive solution and identify its limitations.
    • Think about how to optimize the solution in terms of time and space complexity.
    • Practice solving similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to compute the nth Fibonacci number efficiently using an iterative approach with O(n) time complexity and O(1) space complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free