algoadvance

Leetcode 509. Fibonacci Number Problem Statement:

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 F(n).

Clarifying Questions:

1. What is the maximum value for n that we need to handle?
   • This helps in understanding potential overflow issues or the need for optimization.
2. Is the use of additional data structures (e.g., arrays for memoization) allowed?
   • This helps in choosing between different implementations like recursive, iterative, or dynamic programming approaches.
3. Should the solution be optimized for time complexity or space complexity?
   • This helps in selecting whether to prioritize iterative solutions (which are usually space efficient) or recursive with memoization (which can be more time efficient).

Assuming the value of n can be large (e.g., up to 30) and additional data structures are allowed, we’ll go for an iterative approach which is both time efficient and space efficient.

Strategy:

1. Base Cases Handling:
   • Directly return 0 for n == 0.
   • Directly return 1 for n == 1.
2. Iterative Solution:
   • Use two variables to keep track of the previous two Fibonacci numbers (a and b).
   • Iterate from 2 to n, computing the current Fibonacci number by summing the previous two.

Code:

#include <iostream>

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n = 10; // Example input
    std::cout << "Fibonacci number at position " << n << " is: " << fib(n) << std::endl;
    return 0;
}

Time Complexity:

• Time Complexity: O(n)
  • The iterative solution makes a single pass from 2 to n, so the time complexity is linear with respect to the input n.
• Space Complexity: O(1)
  • The algorithm uses a constant amount of space (only a few integer variables), so the space complexity is considered constant (O(1)).

This code is efficient for calculating Fibonacci numbers even for relatively large values of n and avoids the pitfalls of stack overflow or excessive recomputation that a naive recursive solution might encounter.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?