Fibonacci Number

Problem

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.

The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Formally:

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

Given an integer n, return the nth Fibonacci number.

Implement multiple solutions with different time/space complexities:

1. Recursive (naive)
2. Recursive with memoization
3. Iterative (optimal)

Constraints

• 0 ≤ n ≤ 45
• The answer fits in a 32-bit signed integer

Examples

Example 1

Input:

n = 0

Output:

0

Explanation: F(0) = 0 by definition

Example 2

Input:

n = 1

Output:

1

Explanation: F(1) = 1 by definition

Example 3

Input:

n = 10

Output:

55

Explanation: F(10) = 55. Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Example 4

Input:

n = 20

Output:

6765

Function Signature

def fibonacci(n: int) -> int:
    """
    Calculate the nth Fibonacci number.

    Args:
        n: The index in the Fibonacci sequence (0-indexed)

    Returns:
        The nth Fibonacci number
    """
    pass

Estimated Time

15-20 minutes

Tags

dynamic-programming recursion easy classic interview