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.

   1if (n === 0) {
   2    yield 1;
   3}

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!.

   1for (let i = 1; i <= n; ++i) {
   2    ans *= i;
   3    yield ans;
   4}

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.

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

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.