2803. Factorial Generator


Problem Description

The task is to write a generator function that produces a sequence of factorials for a given integer n. A factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It's denoted as n! and is calculated as n! = n * (n - 1) * (n - 2) * ... * 2 * 1 with the special case of 0! equaling 1. The challenge here involves creating a function that, when invoked, generates each value in the factorial sequence up to n on-demand, rather than computing them all at once.

Intuition

To solve this problem, we use a generator in TypeScript, which allows us to yield values one at a time whenever the generator's next() method is called. This fits our goal perfectly, as we want to produce factorial values in a sequence, without computing them all upfront.

The intuition behind the solution is to maintain a running product that starts at 1 (0! is 1). As we iterate from 1 to n, we multiply the running product by the current number i to get i!, and then we yield this result. This way, we get each factorial value in turnā€”from 1! to n!ā€”and any code using this generator can retrieve the next value in the factorial sequence whenever required without calculating the entire sequence ahead of time.

With this approach, we can efficiently generate factorial values for each step without redundant calculations, using the previously computed value as the foundation for the next.

Solution Approach

To implement the solution, a Generator function in TypeScript is used, identified by the function* syntax and enabling the yield keyword within its body. Here's the step-by-step approach used in the provided solution:

  1. The generator checks if the input n is 0. Since the factorial of 0 is defined as 1, it yields 1 immediately.

    if (n === 0) {
        yield 1;
    }
  2. We declare a variable ans to keep track of the running product of the series, initializing it to 1 (0!).

  3. We use a for loop to iterate from 1 to n. On each iteration, we update ans by multiplying it by the current number i, which effectively calculates i!.

    for (let i = 1; i <= n; ++i) {
        ans *= i;
        yield ans;
    }
  4. During each iteration of the loop, after updating ans to hold the factorial of i, we use yield to produce the current value of ans. This allows the caller to retrieve the values of the factorial sequence one by one on-demand.

The algorithm efficiently computes each factorial value in the sequence by building on the previous value, thus avoiding recomputation of factorials. This is a fundamental principle in dynamic programming, although the solution does not store all previously computed values, just the most recent product.

Data structures:

  • The generator itself serves as a custom iterable data structure, allowing the caller of this function to receive factorial values incrementally.

Patterns used:

  • Generator Pattern - Allows the function to yield multiple values over time, rather than computing them all at once and returning them.
  • Iteration - Uses a simple loop to traverse from 1 to n, aligning with the sequence of factorial calculation.
  • In-place Computation - Updates the ans variable in each iteration which holds the latest factorial value.

Overall, this approach maximizes efficiency minimizing both time and space complexity, as it calculates each factorial product when needed without storing all results or performing redundant calculations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example where n = 4. The goal is to generate the sequence of factorials for the numbers 0 through 4, which are 1, 1, 2, 6, and 24, respectively.

  1. The generator checks if n is 0. In our case, since n is 4, it doesn't yield 1 immediately and moves on to the next steps.

  2. A variable ans is declared and initialized to 1, which represents the factorial for 0 (0!).

  3. We start a loop from 1 up to and including n, which is 4 in our case. In each iteration of the loop, ans would be updated as follows:

    • First Iteration (i = 1):
      • ans *= i ā†’ ans = 1 * 1
      • The generator yields the current value of ans, which is 1.
    • Second Iteration (i = 2):
      • ans *= i ā†’ ans = 1 * 2
      • The generator yields the current value of ans, which is 2.
    • Third Iteration (i = 3):
      • ans *= i ā†’ ans = 2 * 3
      • The generator yields the current value of ans, which is 6.
    • Fourth Iteration (i = 4):
      • ans *= i ā†’ ans = 6 * 4
      • The generator yields the current value of ans, which is 24.
  4. During each iteration, after ans is updated to hold the factorial of i, yield is used to produce the current ans value. This allows the caller to get the factorial values one at a time on-demand.

Assuming the calling code continually invokes the generator's next() method after each value is yielded, it would receive the sequence of factorial values one by one:

  • next() ā†’ 1 (which is 1!)
  • next() ā†’ 2 (which is 2!)
  • next() ā†’ 6 (which is 3!)
  • next() ā†’ 24 (which is 4!)

In real-world usage, this can be very memory efficient, as we compute each factorial as needed without storing every single result. This method is particularly useful when working with very large sequences where memory consumption is a concern.

Solution Implementation

1# This generator function calculates factorial numbers up to n.
2# It yields each intermediate factorial result in the sequence.
3def factorial(n):
4    # Base case: the factorial of 0 is 1.
5    if n == 0:
6        yield 1
7
8    # Initialize the accumulator variable for the factorial calculation.
9    accumulator = 1
10
11    # Iterate from 1 to n, multiplying the accumulator by each number.
12    for i in range(1, n + 1):
13        accumulator *= i
14
15        # Yield the current result of the factorial up to i.
16        yield accumulator
17
18# Usage example:
19# Create an instance of the generator for the factorial of 2.
20generator = factorial(2)
21
22# Retrieve and print the first result from the generator, which is 1! = 1.
23print(next(generator))  # Outputs: 1
24
25# Retrieve and print the second result from the generator, which is 2! = 2.
26print(next(generator))  # Outputs: 2
27
1import java.util.Iterator;
2
3// This class represents an iterable sequence of factorial numbers up to a given n.
4public class FactorialSequence implements Iterable<Integer> {
5    private final int n;
6
7    // Constructor for the FactorialSequence class
8    public FactorialSequence(int n) {
9        this.n = n;
10    }
11
12    // Method to create and return an iterator over the factorial sequence.
13    @Override
14    public Iterator<Integer> iterator() {
15        return new Iterator<>() {
16            private int current = 0;
17            private int accumulator = 1;
18
19            // Checks if the next factorial number is available.
20            @Override
21            public boolean hasNext() {
22                return current <= n;
23            }
24
25            // Computes and returns the next factorial number.
26            @Override
27            public Integer next() {
28                if (current == 0 || current == 1) {
29                    // Factorial of 0 or 1 is always 1.
30                    current++;
31                    return accumulator; // 1
32                } else {
33                    accumulator *= current;
34                    current++;
35                    return accumulator;
36                }
37            }
38        };
39    }
40
41    // Usage example:
42    public static void main(String[] args) {
43        // Create an instance of the factorial sequence for the factorial of 2.
44        FactorialSequence sequence = new FactorialSequence(2);
45
46        // Retrieve and print results from the sequence using an iterator.
47        Iterator<Integer> iterator = sequence.iterator();
48
49        // Retrieve and print the first result from the sequence, which is 1! = 1.
50        System.out.println(iterator.next()); // Outputs: 1
51
52        // Retrieve and print the second result from the sequence, which is 2! = 2.
53        System.out.println(iterator.next()); // Outputs: 2
54    }
55}
56
1#include <iostream>
2#include <vector>
3
4// This class represents a 'generator' for factorial numbers up to 'n' using precomputation.
5class FactorialGenerator {
6private:
7    std::vector<int> factorials;
8    size_t currentIndex;
9
10public:
11    // Constructor that precalculates the factorials up to 'n'.
12    explicit FactorialGenerator(int n) : currentIndex(0) {
13        // Reserve space for the factorial results for optimization.
14        factorials.reserve(n + 1);
15
16        // Base case: the factorial of 0 is 1.
17        factorials.push_back(1);
18
19        // Compute the factorial of each number in the sequence up to 'n' and store the results.
20        int accumulator = 1;
21        for (int i = 1; i <= n; ++i) {
22            accumulator *= i;
23            factorials.push_back(accumulator);
24        }
25    }
26
27    // Function to get the next factorial in the sequence.
28    int next() {
29        // Check if there are more factorials to return.
30        if (currentIndex < factorials.size()) {
31            // Return the next factorial and increment the index.
32            return factorials[currentIndex++];
33        } else {
34            // If there are no more factorials, throw an exception or handle the case as desired.
35            throw std::out_of_range("No more factorials in the sequence.");
36        }
37    }
38
39   // Function to check if there are more factorials to be generated.
40   bool hasNext() const {
41       return currentIndex < factorials.size();
42   }
43};
44
45int main() {
46    // Usage example:
47    // Create an instance of the generator for factorial of 2.
48    FactorialGenerator generator(2);
49
50    // Retrieve and print the first result from the generator, which is 1! = 1.
51    if (generator.hasNext()) {
52        std::cout << generator.next() << std::endl; // Outputs: 1
53    }
54
55    // Retrieve and print the second result from the generator, which is 2! = 2.
56    if (generator.hasNext()) {
57        std::cout << generator.next() << std::endl; // Outputs: 2
58    }
59
60    return 0;
61}
62
1// This generator function calculates factorial numbers up to n.
2// It yields each intermediate factorial result in the sequence.
3function* factorial(n: number): Generator<number> {
4    // Base case: the factorial of 0 is 1.
5    if (n === 0) {
6        yield 1;
7    }
8
9    // Initialize the accumulator variable for the factorial calculation.
10    let accumulator = 1;
11
12    // Iterate from 1 to n, multiplying the accumulator by each number.
13    for (let i = 1; i <= n; ++i) {
14        accumulator *= i;
15
16        // Yield the current result of the factorial up to i.
17        yield accumulator;
18    }
19}
20
21// Usage example:
22// Create an instance of the generator (iterator) for factorial of 2.
23const generator = factorial(2);
24
25// Retrieve and print the first result from the generator, which is 1! = 1.
26console.log(generator.next().value); // Outputs: 1
27
28// Retrieve and print the second result from the generator, which is 2! = 2.
29console.log(generator.next().value); // Outputs: 2
30

Time and Space Complexity

The time complexity of this generator function is O(n). This is because the loop within the generator runs n times, with each iteration involving a constant number of operations (a multiplication and a yield). Therefore, the overall number of operations linearly depends on the input n.

The space complexity of the generator is O(1). This is because the space required by the generator does not grow with the input n. It uses a fixed amount of space to store the local variables (ans, i) regardless of the size of n. The fact that this function yields the factorial of n in each iteration does not add to the space complexity because the generated values are not stored in memory; they are produced on-demand.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More