Generate Fibonacci Sequence

Difficulty: Easy | Acceptance: 83.70% | Paid: No Topics: N/A

Write a generator function that yields the Fibonacci sequence. 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. The generator should yield 0, 1, 1, 2, 3, 5, 8, … indefinitely.

• Examples
• Constraints
• Generator Approach
• Iterative Approach
• Recursive Approach

Examples

Example 1

Input: gen = fib_generator()
Output: [0, 1, 1, 2, 3]
Explanation:
gen.next() returns 0
gen.next() returns 1
gen.next() returns 1
gen.next() returns 2
gen.next() returns 3

Example 2

Input: gen = fib_generator()
Output: [0, 1, 1, 2, 3, 5, 8, 13]
Explanation:
gen.next() returns 0
gen.next() returns 1
gen.next() returns 1
gen.next() returns 2
gen.next() returns 3
gen.next() returns 5
gen.next() returns 8
gen.next() returns 13

Constraints

0 <= n <= 10⁴

Generator Approach

Intuition Use the built-in generator/yield functionality to lazily compute Fibonacci numbers one at a time.

Steps

• Initialize two variables a = 0 and b = 1
• In an infinite loop, yield a and then update a, b = b, a + b

def fib_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Complexity

• Time: O(1) per call to next()
• Space: O(1)
• Notes: This is the most efficient approach as it uses constant space and constant time per call.

Iterative Approach

Intuition Maintain state between calls and compute the next Fibonacci number iteratively.

Steps

• Initialize two variables a = 0 and b = 1 in the constructor
• In the next() method, return a and then update a, b = b, a + b

class FibGenerator:
    def __init__(self):
        self.a = 0
        self.b = 1
    
    def next(self):
        result = self.a
        self.a, self.b = self.b, self.a + self.b
        return result

Complexity

• Time: O(1) per call to next()
• Space: O(1)
• Notes: This approach is similar to the generator approach but uses a class to maintain state.

Recursive Approach

Intuition Use recursion to compute Fibonacci numbers, with memoization to avoid redundant calculations.

Steps

• Use memoization to store computed Fibonacci numbers
• For each call to next(), compute the next Fibonacci number using recursion

class FibGenerator:
    def __init__(self):
        self.memo = {0: 0, 1: 1}
        self.n = 0
    
    def fib(self, n):
        if n not in self.memo:
            self.memo[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.memo[n]
    
    def next(self):
        result = self.fib(self.n)
        self.n += 1
        return result

Complexity

• Time: O(1) per call to next() after memoization
• Space: O(n) for memoization
• Notes: This approach uses more space due to memoization but is still efficient for repeated calls.