Fibonacci in C++

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.

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:

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