Problem Description

The Fibonacci sequence is a famous mathematical sequence where each number is the sum of the two numbers that come before it. The sequence starts with 0 and 1.

The sequence follows this pattern:

• F(0) = 0 (the first number is 0)
• F(1) = 1 (the second number is 1)
• For any position n > 1: F(n) = F(n-1) + F(n-2)

For example:

• F(2) = F(1) + F(0) = 1 + 0 = 1
• F(3) = F(2) + F(1) = 1 + 1 = 2
• F(4) = F(3) + F(2) = 2 + 1 = 3
• F(5) = F(4) + F(3) = 3 + 2 = 5

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

Given an integer n, your task is to calculate and return the value of F(n), which is the n-th Fibonacci number in the sequence.

The solution uses an iterative approach with two variables a and b to track consecutive Fibonacci numbers. Starting with a = 0 and b = 1, it performs n iterations where in each step it updates the values by shifting: the new a becomes the old b, and the new b becomes the sum of the old a and b. After n iterations, variable a holds the n-th Fibonacci number.

Intuition

The key observation is that to calculate any Fibonacci number, we only need to know the two numbers immediately before it. We don't need to store the entire sequence.

Think about how we would calculate F(5) manually:

• Start with F(0) = 0 and F(1) = 1
• To get F(2), we add these: 0 + 1 = 1
• To get F(3), we need F(2) + F(1) = 1 + 1 = 2
• To get F(4), we need F(3) + F(2) = 2 + 1 = 3
• To get F(5), we need F(4) + F(3) = 3 + 2 = 5

Notice that at each step, we only care about the last two numbers. Once we've used F(0) and F(1) to get F(2), we never need F(0) again. This pattern continues throughout the calculation.

This leads us to use a "sliding window" approach with just two variables. We can think of these two variables as a window that slides through the Fibonacci sequence:

• Initially: a = 0 (represents F(0)), b = 1 (represents F(1))
• After 1 iteration: a = 1 (represents F(1)), b = 1 (represents F(2))
• After 2 iterations: a = 1 (represents F(2)), b = 2 (represents F(3))
• And so on...

The elegant part is the simultaneous assignment a, b = b, a + b. This single line captures the essence of the Fibonacci recurrence: the current number becomes the previous number, and the next number becomes the sum of the current and previous. After n such shifts, variable a will contain F(n).

Learn more about Recursion, Memoization, Math and Dynamic Programming patterns.

Solution Approach

The solution uses an iterative approach with two variables to efficiently compute the n-th Fibonacci number.

We initialize two variables:

• a = 0 - represents the current Fibonacci number in our iteration
• b = 1 - represents the next Fibonacci number

The core algorithm performs n iterations. In each iteration, we update both variables simultaneously:

a, b = b, a + b

This simultaneous assignment does two things:

1. Moves b (the next number) to become a (the current number)
2. Calculates the new next number as a + b and stores it in b

Let's trace through an example for n = 4:

• Initial state: a = 0, b = 1
• Iteration 1: a = 1, b = 0 + 1 = 1
• Iteration 2: a = 1, b = 1 + 1 = 2
• Iteration 3: a = 2, b = 1 + 2 = 3
• Iteration 4: a = 3, b = 2 + 3 = 5
• Return a = 3, which is F(4)

The pattern here is that after k iterations, a holds F(k) and b holds F(k+1). Therefore, after n iterations, a contains exactly F(n).

This approach has a time complexity of O(n) since we perform exactly n iterations, and a space complexity of O(1) as we only use two variables regardless of the input size. This is much more efficient than a recursive approach which would have O(2^n) time complexity without memoization, or require O(n) extra space with memoization.

Example Walkthrough

Let's walk through calculating F(6) using the iterative approach with two variables.

Goal: Find the 6th Fibonacci number

Initial Setup:

• a = 0 (represents F(0))
• b = 1 (represents F(1))
• We need to perform 6 iterations

Step-by-step execution:

Iteration 1: a, b = b, a + b

• New a = old b = 1
• New b = old a + old b = 0 + 1 = 1
• State: a = 1, b = 1 (now a holds F(1))

Iteration 2: a, b = b, a + b

• New a = old b = 1
• New b = old a + old b = 1 + 1 = 2
• State: a = 1, b = 2 (now a holds F(2))

Iteration 3: a, b = b, a + b

• New a = old b = 2
• New b = old a + old b = 1 + 2 = 3
• State: a = 2, b = 3 (now a holds F(3))

Iteration 4: a, b = b, a + b

• New a = old b = 3
• New b = old a + old b = 2 + 3 = 5
• State: a = 3, b = 5 (now a holds F(4))

Iteration 5: a, b = b, a + b

• New a = old b = 5
• New b = old a + old b = 3 + 5 = 8
• State: a = 5, b = 8 (now a holds F(5))

Iteration 6: a, b = b, a + b

• New a = old b = 8
• New b = old a + old b = 5 + 8 = 13
• State: a = 8, b = 13 (now a holds F(6))

Result: Return a = 8

We can verify this is correct: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, ... and F(6) = 8.

Notice how at each iteration, we're essentially sliding our two-variable window forward through the Fibonacci sequence. The variable a always contains the Fibonacci number at position equal to the iteration count, while b stays one step ahead, ready to help calculate the next number.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the given integer. This is because the code uses a single for loop that iterates exactly n times, and within each iteration, it performs constant-time operations (variable assignments).

The space complexity is O(1). The algorithm only uses two variables a and b to store intermediate Fibonacci values, regardless of the input size n. No additional data structures or recursive call stack space is used, making the space usage constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Loop Iteration Count

A common mistake is misunderstanding how many iterations are needed. Some might think we need n-1 or n+1 iterations instead of exactly n.

Incorrect Implementation:

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n - 1):  # Wrong! This would return F(n-1)
        a, b = b, a + b
    return a

Why it happens: Confusion about whether we're counting from 0 or 1, or whether the initial state counts as an iteration.

Solution: Remember that we start at F(0) and need exactly n steps to reach F(n). Test with small values: for n=0, we need 0 iterations to stay at F(0)=0; for n=1, we need 1 iteration to reach F(1)=1.

2. Incorrect Variable Order in Simultaneous Assignment

The order of variables in the tuple assignment matters significantly.

Incorrect Implementation:

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = a + b, b  # Wrong order! This breaks the algorithm
    return a

Why it happens: Not understanding that a, b = b, a + b evaluates the entire right side before any assignment occurs.

Solution: Always use a, b = b, a + b where the new a gets the old b, and the new b gets the sum of old a and old b.

3. Using Sequential Assignment Instead of Simultaneous

Attempting to update variables one at a time loses the original values needed for calculation.

Incorrect Implementation:

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a = b           # Now we've lost the original value of 'a'
        b = a + b       # This uses the new 'a', not the original!
    return a

Why it happens: Not realizing that sequential assignment changes the first variable before the second calculation.

Solution: Either use simultaneous assignment a, b = b, a + b or store the old value in a temporary variable:

temp = a
a = b
b = temp + b

4. Edge Case Handling for n=0

Some implementations fail to handle the base case where n=0 correctly.

Incorrect Implementation:

def fib(n: int) -> int:
    if n == 0:
        return 0
    a, b = 1, 1  # Starting with F(1) and F(2) instead of F(0) and F(1)
    for _ in range(n - 1):
        a, b = b, a + b
    return a

Why it happens: Trying to optimize by handling n=0 separately but then incorrectly adjusting the starting values and iteration count.

Solution: The beauty of the original solution is that it handles n=0 naturally without special cases. Starting with a=0, b=1 and iterating exactly n times works for all non-negative values of n.