2648. Generate Fibonacci Sequence

Easy

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

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 the function* syntax. This indicates that the function will be a generator.
Inside the function, we initialize two variables a and b to start the Fibonacci sequence. a starts at 0, and b starts at 1.
We then enter an infinite while loop with the condition true. This loop will run indefinitely until the consumer of the generator decides to stop requesting values.
Inside the loop, we yield a. The yield keyword is what makes this function a generator. It pauses the function execution and sends the value of a to the consumer. When the consumer asks for the next value, the function resumes execution right after the yield 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 of b, and b is updated to the sum of the old a and b.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example 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 the fibGenerator() function.
We call gen.next().value for the first time:

a. The generator function starts executing and initializes a to 0 and b to 1.

b. It enters the infinite while loop.

c. It hits the yield a statement. At this point, a is 0, so it yields 0.

d. The gen.next().value call returns 0, 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 in a = 1 and b = 1.

c. The next iteration of the loop starts, and yield a yields 1.

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 and b again. Now a = 1 (previous b) and b = 2 (previous a + b).

b. It yields a, which is 1.

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 return 2, 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

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2648. Generate Fibonacci Sequence

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings