Generate Fibonacci Sequence Problem

Problem

Write a generator function that returns a generator object which yields the fibonacci sequence.

The fibonacci sequence is defined by the relation Xn = Xn-1 + Xn-2.

The first few numbers of the series are 0, 1, 1, 2, 3, 5, 8, 13.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input:
callCount = 5
Output:
 [0,1,1,2,3]
Explanation:
const gen = fibGenerator();
gen.next().value; // 0
gen.next().value; // 1
gen.next().value; // 1
gen.next().value; // 2
gen.next().value; // 3

Example 2:

1
2
3
4
5


Input:
callCount = 0
Output:
 []
Explanation: gen.next() is never called so nothing is outputted

Solution

Method 1 – Generator Function with State Variables

Intuition

A generator function can maintain its own state between calls. For the Fibonacci sequence, we only need to remember the last two numbers to generate the next one. By yielding each value and updating the state, we can produce the sequence indefinitely.

Approach

Initialize two variables, a and b, to 0 and 1 (the first two Fibonacci numbers).
Use an infinite loop to yield a and update a and b to the next Fibonacci numbers.
Each call to .next() on the generator will yield the next Fibonacci number.

Code

1
2
3
4
5
6
7


function* fibGenerator() {
    let a = 0, b = 1;
    while (true) {
        yield a;
        [a, b] = [b, a + b];
    }
}

1
2
3
4
5
6
7


function* fibGenerator(): Generator<number, void, unknown> {
    let a = 0, b = 1;
    while (true) {
        yield a;
        [a, b] = [b, a + b];
    }
}

Complexity

⏰ Time complexity: O(1) per call to .next(), since only a constant number of operations are performed for each value.
🧺 Space complexity: O(1), as only two variables are maintained regardless of how many numbers are generated.

Generate Fibonacci Sequence Problem#

Problem#

Examples#

Solution#

Method 1 – Generator Function with State Variables#

Intuition#

Approach#

Code#

Complexity#