Domain 1EasyCORE

Fibonacci Number

The problem asks us to compute the nth Fibonacci number, where the sequence starts with F(0) = 0 and F(1) = 1, and each subsequent number is the sum of the two preceding ones. The input is a single integer `n` (where 0 <= n <= 30), and the output should be the nth Fibonacci number.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

509. Fibonacci Number

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 67.5%


Problem Breakdown

The problem asks us to compute the nth Fibonacci number, where the sequence starts with F(0) = 0 and F(1) = 1, and each subsequent number is the sum of the two preceding ones. The input is a single integer n (where 0 <= n <= 30), and the output should be the nth Fibonacci number.

Inputs:

  • An integer n

Outputs:

  • The nth Fibonacci number

Implicit Constraints/Edge Cases:

  • If n is 0, the function should return 0.
  • If n is 1, the function should return 1.
  • The constraint 0 <= n <= 30 ensures that we won’t encounter overflow issues with standard integer types.

Intuition

The brute-force approach to solving this problem would be to use a recursive function that directly implements the Fibonacci sequence definition. However, this approach has exponential time complexity (O(2^n)) due to repeated calculations of the same Fibonacci numbers.

A better approach is to use dynamic programming or an iterative method to avoid redundant calculations. By storing previously computed Fibonacci numbers, we can reduce the time complexity to linear (O(n)) and keep the space complexity manageable.

Approach

We’ll use an iterative approach with a constant amount of extra space. This involves maintaining two variables to store the last two Fibonacci numbers and updating them as we iterate from 2 to n.

  1. Initialize two variables, a and b, to represent F(0) and F(1), respectively.
  2. If n is 0, return a.
  3. If n is 1, return b.
  4. Iterate from 2 to n:
    • Compute the next Fibonacci number as the sum of a and b.
    • Update a to be b, and b to be the newly computed Fibonacci number.
  5. After the loop, b will contain F(n), which we return.

Complexity Analysis

  • Time Complexity: O(n) because we iterate from 2 to n once.
  • Space Complexity: O(1) because we only use a constant amount of extra space (two variables).

Solution

def fib(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Edge Cases Handled

  • n = 0: The function returns 0 as expected.
  • n = 1: The function returns 1 as expected.
  • n = 2 to n = 30: The function correctly computes the Fibonacci number for each value within the given range.