Problem Description

This problem asks you to create a generator function that produces the factorial sequence up to a given number n.

The factorial of a number is the product of all positive integers from 1 up to that number. For example:

• 1! = 1
• 2! = 2 × 1 = 2
• 3! = 3 × 2 × 1 = 6
• 4! = 4 × 3 × 2 × 1 = 24

The special case is that 0! = 1 by definition.

Your generator function should:

1. Take an integer n as input
2. Yield each factorial value in sequence from 1! to n!

For instance, if n = 3, the generator should yield:

• First yield: 1 (which is 1!)
• Second yield: 2 (which is 2! = 2 × 1)
• Third yield: 6 (which is 3! = 3 × 2 × 1)

If n = 0, the generator should yield only 1 (since 0! = 1).

The solution uses a simple iterative approach where it maintains a running product (ans), multiplying it by each successive integer from 1 to n, and yielding the result at each step. This efficiently generates the factorial sequence without recalculating each factorial from scratch.

Intuition

The key insight is recognizing that each factorial builds upon the previous one. Rather than calculating each factorial from scratch (which would be inefficient), we can use the relationship that n! = n × (n-1)!.

When generating the sequence 1!, 2!, 3!, ..., n!, we notice:

• 1! = 1
• 2! = 2 × 1 = 2 × 1!
• 3! = 3 × 2 × 1 = 3 × 2!
• 4! = 4 × 3 × 2 × 1 = 4 × 3!

This pattern shows that each factorial is simply the previous factorial multiplied by the current number. This leads us to maintain a running product that we update at each step.

Since we need to output intermediate results (not just the final n!), a generator function is perfect for this task. Generators allow us to produce values one at a time, pausing execution between yields, which matches our need to output each factorial in the sequence.

The approach becomes straightforward:

1. Start with ans = 1 (which represents 0!)
2. For each number i from 1 to n:
   • Multiply ans by i to get i!
   • Yield this value
   • Continue to the next iteration

The special case of n = 0 is handled separately since there's no multiplication involved - we simply yield 1 directly.

This incremental calculation approach has optimal time complexity since each factorial is computed in constant time relative to the previous one, rather than recalculating all multiplications from the beginning.

Solution Approach

The implementation uses a generator function with a simple iterative approach to build the factorial sequence incrementally.

Step-by-step walkthrough:

1. Handle the special case: First, we check if n === 0. Since 0! = 1 by definition and there's no sequence to generate, we simply yield 1 and return.

2. Initialize the accumulator: We start with ans = 1, which will store our running factorial value.

3. Iterative multiplication: We loop from i = 1 to i = n:

   • Multiply the current ans by i: ans *= i
   • This gives us i! since ans previously held (i-1)!
   • Yield the current factorial value
   • Continue to the next iteration

Code implementation:

function* factorial(n: number): Generator<number> {
    if (n === 0) {
        yield 1;
    }
    let ans = 1;
    for (let i = 1; i <= n; ++i) {
        ans *= i;
        yield ans;
    }
}

Example execution for n = 3:

• Initially: ans = 1
• Iteration 1: i = 1, ans = 1 × 1 = 1, yield 1
• Iteration 2: i = 2, ans = 1 × 2 = 2, yield 2
• Iteration 3: i = 3, ans = 2 × 3 = 6, yield 6

The generator pauses after each yield statement, allowing the caller to retrieve values one at a time using gen.next().value. This lazy evaluation pattern is memory-efficient and provides values on-demand rather than computing and storing the entire sequence upfront.

Time Complexity: O(n) - we perform n iterations Space Complexity: O(1) - we only maintain a single variable ans regardless of input size

Example Walkthrough

Let's walk through the solution with n = 4 to see how the generator produces the factorial sequence.

Initial Setup:

• Input: n = 4
• We want to generate: 1!, 2!, 3!, 4!
• Initialize ans = 1

Step-by-step execution:

Iteration 1 (i = 1):
- Current ans: 1
- Calculate: ans = ans × i = 1 × 1 = 1
- Yield: 1 (this is 1!)
- Generator pauses

Iteration 2 (i = 2):
- Current ans: 1 (from previous)
- Calculate: ans = ans × i = 1 × 2 = 2
- Yield: 2 (this is 2!)
- Generator pauses

Iteration 3 (i = 3):
- Current ans: 2 (from previous)
- Calculate: ans = ans × i = 2 × 3 = 6
- Yield: 6 (this is 3!)
- Generator pauses

Iteration 4 (i = 4):
- Current ans: 6 (from previous)
- Calculate: ans = ans × i = 6 × 4 = 24
- Yield: 24 (this is 4!)
- Generator completes

Usage example:

const gen = factorial(4);
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2
console.log(gen.next().value); // 6
console.log(gen.next().value); // 24
console.log(gen.next().done);  // true

Notice how each factorial builds on the previous one - we never recalculate from scratch. The value 6 (which is 3!) is obtained by multiplying the previous result 2 (which was 2!) by 3, demonstrating the efficiency of maintaining a running product.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) per complete iteration through all yielded values.

The generator function performs n iterations in the for loop (from i = 1 to i = n). Each iteration involves:

• One multiplication operation (ans *= i): O(1)
• One yield operation: O(1)

Therefore, to generate all factorial values from 1! to n!, the total time complexity is O(n).

Note: If we consider individual next() calls, each call has O(1) amortized time complexity since the generator maintains its state between calls.

Space Complexity: O(1)

The generator function uses constant extra space:

• One variable ans to store the current factorial value
• One loop counter variable i
• The generator object itself maintains minimal state information

The generator yields values one at a time rather than storing all factorial values in memory, making it memory-efficient regardless of the value of n.

Common Pitfalls

1. Forgetting to Handle the n=0 Case

A common mistake is omitting the special case for n = 0. Without this check, the generator would yield nothing when n = 0, which is incorrect since 0! = 1.

Incorrect Implementation:

def factorial(n):
    factorial_value = 1
    for i in range(1, n + 1):  # When n=0, range(1, 1) produces no iterations
        factorial_value *= i
        yield factorial_value
    # Nothing is yielded when n=0!

Solution: Always include the base case check at the beginning of the function.

2. Integer Overflow for Large Values

While Python handles arbitrarily large integers automatically, in other languages or when dealing with very large factorials, overflow can occur. For example, 20! = 2,432,902,008,176,640,000 which exceeds the range of many integer types.

Solution:

• In Python, this is handled automatically
• In other languages, consider using BigInteger types or implement overflow checking
• Document the practical limits of your implementation

3. Yielding at the Wrong Time

Some developers might yield before multiplying, causing off-by-one errors:

Incorrect Implementation:

def factorial(n):
    if n == 0:
        yield 1
        return
  
    factorial_value = 1
    yield factorial_value  # This yields 1 before any multiplication!
    for i in range(1, n + 1):
        factorial_value *= i
        yield factorial_value
    # This yields n+1 values instead of n values

Solution: Ensure you multiply first, then yield, to get the correct sequence.

4. Not Understanding Generator Exhaustion

Once a generator is exhausted, it won't restart automatically:

gen = factorial(3)
values = list(gen)  # [1, 2, 6]
more_values = list(gen)  # [] - generator is exhausted!

Solution: Create a new generator instance when you need to iterate again, or store the results if you need to reuse them multiple times.