2648. Generate Fibonacci Sequence
Problem Description
The task is to implement a generator function in TypeScript that produces a generator object capable of yielding values from the Fibonacci sequence indefinitely. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. That is to say, X_n = X_(n-1) + X_(n-2)
for n
greater than 1, with X_0
being 0 and X_1
being 1. The function we create should be able to produce each Fibonacci number when requested.
Intuition
To solve this problem, we have to understand what a generator is and how it works. A generator in TypeScript is a function that can be paused and resumed, and it produces a sequence of results instead of a single value. This fits perfectly with the requirement to yield an indefinite sequence, like the Fibonacci series, since we don't want to compute all the numbers at once, which would be inefficient and impractical for a potentially infinite series.
The intuition behind the Fibonacci sequence generator is relatively straightforward. We start with two variables, a
and b
, which represent the two latest numbers in the sequence. We initialize a
to 0 and b
to 1, which are the first two numbers in the Fibonacci sequence. In each iteration of our generator function, we yield the current value of a
, which is part of the sequence, and then update a
and b
to the next two numbers.
This update is done by setting a
to b
and b
to a + b
, effectively shifting the sequence by one. The array destructuring syntax [a, b] = [b, a + b]
in TypeScript makes this step concise and clear. Because our generator is designed to run indefinitely and the Fibonacci sequence has no end, we enclose our logic in an infinite while
loop. This allows consumers of the generator to keep requesting the next number in the sequence for as long as they need without ever running out of values to yield.
Solution Approach
The implementation of the Fibonacci sequence generator is elegantly simple, leaning heavily on the capabilities of TypeScript's generator functions. The generator pattern is ideal for this kind of problem since it allows for the creation of a potentially infinite sequence where each element is produced on demand.
Here's a breakdown of the algorithm step by step:
-
We first declare a generator function
fibGenerator
by using thefunction*
syntax. This indicates that the function will be a generator. -
Inside the function, we initialize two variables
a
andb
to start the Fibonacci sequence.a
starts at0
, andb
starts at1
. -
We then enter an infinite
while
loop with the conditiontrue
. This loop will run indefinitely until the consumer of the generator decides to stop requesting values. -
Inside the loop, we
yield a
. Theyield
keyword is what makes this function a generator. It pauses the function execution and sends the value ofa
to the consumer. When the consumer asks for the next value, the function resumes execution right after theyield
statement. -
After yielding
a
, we perform the Fibonacci update step using array destructuring:[a, b] = [b, a + b]
. This step calculates the next Fibonacci number by summing the two most recent numbers in the sequence.a
is updated to the current value ofb
, andb
is updated to the sum of the olda
andb
. -
The loop then iterates, and the process repeats, yielding the next number in the Fibonacci sequence.
By using a generator function, we can maintain the state of our sequence (the last two numbers) across multiple calls to .next()
. We avoid having to store the entire sequence in memory, which allows the function to produce Fibonacci numbers as far into the sequence as the consumer requires without any predetermined limits.
The fibGenerator
generator function can be used by creating a generator object, say gen
, and repeatedly calling gen.next().value
to get the next number in the Fibonacci sequence. This process can go on as long as needed to generate Fibonacci numbers on the fly.
There are no complex data structures needed: the algorithm only ever keeps track of the two most recent values. This is an excellent example of how a generator can manage state internally without the need for external data structures or class properties.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's manually walk through the initial part of running our generator function fibGenerator
.
-
A generator object
gen
is created by calling thefibGenerator()
function. -
We call
gen.next().value
for the first time:a. The generator function starts executing and initializes
a
to0
andb
to1
.b. It enters the infinite
while
loop.c. It hits the
yield a
statement. At this point,a
is0
, so it yields0
.d. The
gen.next().value
call returns0
, which is the first number in the Fibonacci sequence. -
We call
gen.next().value
for the second time:a. The generator function resumes execution right after the
yield
statement.b. The Fibonacci update happens:
[a, b] = [b, a + b]
results ina = 1
andb = 1
.c. The next iteration of the loop starts, and
yield a
yields1
.d. The call returns
1
, which is the second number in the Fibonacci sequence. -
We call
gen.next().value
for the third time:a. The function resumes and updates
a
andb
again. Nowa = 1
(previousb
) andb = 2
(previousa + b
).b. It yields
a
, which is1
.c. The call returns
1
, which is the third Fibonacci number. -
This process can continue indefinitely, with
gen.next().value
being called to get the next Fibonacci number each time. The next few calls would return2
,3
,5
,8
,13
, and so on.
Each call to .next()
incrementally advances the generator function's internal state, computes the next Fibonacci number, and yields it until the next call. By following these steps, we don't calculate all the Fibonacci numbers at once, nor do we run out of numbers to yield ā respecting the definition of an infinite series.
Solution Implementation
1def fib_generator():
2 """
3 A generator function that yields Fibonacci numbers indefinitely.
4 """
5 current = 0 # The current number in the sequence, initialized to 0.
6 next_num = 1 # The next number in the sequence, initialized to 1.
7
8 while True:
9 # Yield the current number before updating.
10 yield current
11 # Update the current and the next number with the next Fibonacci numbers.
12 current, next_num = next_num, current + next_num
13
14
15# Example usage:
16generator = fib_generator() # Create a new Fibonacci sequence generator.
17print(next(generator)) # Outputs 0, the first number in the sequence.
18print(next(generator)) # Outputs 1, the second number in the sequence.
19# To continue obtaining values from the generator, repeatedly call next(generator).
20
1import java.util.Iterator;
2
3// Class that implements an Iterator to generate Fibonacci numbers indefinitely.
4public class FibGenerator implements Iterator<Integer> {
5
6 private int current = 0; // The current number in the sequence, initialized to 0.
7 private int next = 1; // The next number in the sequence, initialized to 1.
8
9 // hasNext method is always true since Fibonacci sequence is infinite.
10 @Override
11 public boolean hasNext() {
12 return true; // Fibonacci numbers can be generated indefinitely.
13 }
14
15 // The next method returns the current number in the sequence and advances.
16 @Override
17 public Integer next() {
18 int temp = current; // To store the current number to be returned.
19 current = next; // Update current to the next number in sequence.
20 next = next + temp; // Calculate the next number in the sequence and update.
21 return temp; // Return the previous value of current.
22 }
23}
24
25/*
26// Example usage:
27FibGenerator generator = new FibGenerator(); // Create a new Fibonacci sequence generator.
28System.out.println(generator.next()); // Outputs 0, the first number in the sequence.
29System.out.println(generator.next()); // Outputs 1, the second number in the sequence.
30// To continue obtaining values from the generator, call generator.next().
31*/
32
1#include <iostream>
2#include <tuple>
3
4// A generator-like class for Fibonacci numbers.
5class FibGenerator {
6public:
7 // Constructor initializes the first two Fibonacci numbers.
8 FibGenerator() : current(0), next(1) {}
9
10 // The function that returns the next Fibonacci number.
11 int getNext() {
12 int returnValue = current; // The value to be returned.
13
14 // Update the current and next number to the next pair in the Fibonacci sequence.
15 std::tie(current, next) = std::make_pair(next, current + next);
16
17 return returnValue; // Return the current Fibonacci number.
18 }
19
20private:
21 int current; // The current number in the sequence.
22 int next; // The next number in the sequence.
23};
24
25/*
26// Example usage:
27int main() {
28 FibGenerator generator; // Create a new Fibonacci sequence generator.
29
30 std::cout << generator.getNext() << std::endl; // Outputs 0, the first number in the sequence.
31 std::cout << generator.getNext() << std::endl; // Outputs 1, the second number in the sequence.
32
33 // To continue obtaining values from the generator, call generator.getNext().
34
35 return 0;
36}
37*/
38
1// A generator function that yields Fibonacci numbers indefinitely.
2function* fibGenerator(): Generator<number> {
3 let current = 0; // The current number in the sequence, initialized to 0.
4 let next = 1; // The next number in the sequence, initialized to 1.
5
6 // An infinite loop to continuously yield Fibonacci numbers.
7 while (true) {
8 yield current; // Yield the current number.
9 [current, next] = [next, current + next]; // Update the current and next numbers.
10 }
11}
12
13/*
14// Example usage:
15const generator = fibGenerator(); // Create a new Fibonacci sequence generator.
16console.log(generator.next().value); // Outputs 0, the first number in the sequence.
17console.log(generator.next().value); // Outputs 1, the second number in the sequence.
18// To continue obtaining values from the generator, call generator.next().value.
19*/
20
Time and Space Complexity
Time Complexity
The time complexity of the fibGenerator
function is O(n)
for generating the first n
Fibonacci numbers. This is because the generator yields one Fibonacci number per iteration, and the computation of the next number is a constant-time operation (simple addition and assignment).
Space Complexity
The space complexity of the generator is O(1)
. The function maintains a fixed number of variables (a
and b
) regardless of the number of Fibonacci numbers generated, so it does not use additional space that grows with n
.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!