We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Fibonacci Number

Number: 1013

Difficulty: Easy

Paid? No

Companies: Amazon, Meta, Apple, Microsoft, Google, tcs, Accenture, Bloomberg, Nvidia, Infosys, Yahoo, Cognizant, Zoho

Problem Description

Given a non-negative integer n, calculate F(n) where F(n) represents the nth Fibonacci number. The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n > 1.

Key Insights

  • The Fibonacci sequence is defined recursively.
  • A direct recursive solution can lead to redundant calculations.
  • An iterative or dynamic programming (DP) approach can efficiently compute the result.
  • For n in the range [0, 30], an iterative solution with O(n) time complexity is both simple and effective.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We solve the problem using an iterative approach which computes the Fibonacci numbers starting from 0 and 1 and then iteratively builds up to F(n). This method uses constant space by only keeping track of the last two computed Fibonacci values. The algorithm is efficient and avoids the pitfalls of recursive stack overflow or repeated calculations that would result from a naive recursion.

Code Solutions

# Function to compute the nth Fibonacci number
def fibonacci(n):
    # If n is 0, return 0 directly
    if n == 0:
        return 0
    # Initialize first two Fibonacci numbers
    a, b = 0, 1
    # Iterate from 2 up to n (inclusive)
    for i in range(2, n + 1):
        # Compute the next Fibonacci number by summing the last two
        a, b = b, a + b  # Update a and b for the next iteration
    # For n=1, b already equals 1; for other n, result stored in b
    return b

# Example usage:
print(fibonacci(4))  # Expected output: 3
← Back to All Questions