LeetCode Problem 2803

Difficulty: 🟢 Easy
Topics: —

Solution

LeetCode 2803 - Factorial Generator

Problem Understanding

This problem asks us to implement a generator that produces the factorial sequence up to a given integer n.

Recall that the factorial of a positive integer is defined as:

$$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$$

Additionally, by definition:

$$0! = 1$$

The generator should not return only the final factorial value. Instead, it must yield every factorial value from 1! through n!.

For example, if n = 5, the generator should yield:

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120

Thus the generated sequence is:

[1, 2, 6, 24, 120]

The special case is n = 0. Since 0! = 1, the generator should yield a single value:

[1]

The constraint 0 <= n <= 18 tells us that the input size is extremely small. Even 18! comfortably fits within JavaScript's safe integer range, which is why the problem uses this upper bound. Performance is not a concern here, but we should still produce the sequence efficiently.

The most important edge cases are:

• n = 0, where only 1 should be yielded.
• n = 1, where the sequence contains exactly one value, 1.
• Larger values such as n = 18, where factorial values become large but remain within the supported range.

Approaches

Brute Force

A straightforward approach is to compute each factorial independently.

For every integer i from 1 to n, we could calculate i! by multiplying all numbers from 1 through i, then yield the result.

For example, when computing 5!, we would perform:

• 1 × 2 × 3 × 4 × 5

Even though we already computed 4! earlier, this approach repeats all the work from scratch.

This method is correct because the factorial definition directly specifies how each value should be computed. However, it performs many redundant multiplications.

Key Insight

Successive factorials are closely related:

$$(i+1)! = i! \times (i+1)$$

Once we know i!, we can obtain the next factorial with a single multiplication.

For example:

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

Therefore, we can maintain a running factorial value and update it incrementally as we iterate from 1 to n.

This avoids recomputing previous multiplications and allows the generator to produce each factorial in constant additional work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes each factorial independently
Optimal	O(n)	O(1)	Maintains a running factorial value

Algorithm Walkthrough

Optimal Algorithm

1. Handle the special case where n == 0.

• Since 0! = 1, yield 1 and stop.

2. Initialize a variable factorial_value to 1.

• This represents the current factorial being built.

3. Iterate from 1 through n.

• Each iteration corresponds to computing the next factorial.

4. Update the running factorial.

• Multiply factorial_value by the current number.
• After multiplication, factorial_value equals the current factorial.

5. Yield the updated factorial value.

• This produces the next value in the factorial sequence.

6. Continue until all values from 1! through n! have been generated.

Why it works

The algorithm maintains the invariant that before yielding during iteration i, factorial_value equals i!.

Initially, factorial_value = 1, which corresponds to 1!. At each step, we multiply the previous factorial by the next integer. Since factorials satisfy the recurrence:

$$i! = (i-1)! \times i$$

the invariant remains true throughout the loop. Therefore every yielded value is exactly the correct factorial, and the generated sequence is correct.

Python Solution

from typing import Generator

class Solution:
    def factorial(self, n: int) -> Generator[int, None, None]:
        if n == 0:
            yield 1
            return

        factorial_value = 1

        for number in range(1, n + 1):
            factorial_value *= number
            yield factorial_value

Implementation Explanation

The first step handles the special case n == 0. The factorial of zero is defined as 1, so the generator yields 1 and immediately returns.

For all other values, we initialize factorial_value to 1. This variable stores the most recently computed factorial.

The loop runs from 1 through n. During each iteration, the current number is multiplied into factorial_value, producing the next factorial in the sequence. The updated value is then yielded.

Because every factorial is derived from the previous one using a single multiplication, the implementation performs only n multiplications in total.

Go Solution

func factorial(n int) chan int {
	ch := make(chan int)

	go func() {
		defer close(ch)

		if n == 0 {
			ch <- 1
			return
		}

		factorialValue := 1

		for number := 1; number <= n; number++ {
			factorialValue *= number
			ch <- factorialValue
		}
	}()

	return ch
}

Go-Specific Notes

Go does not have JavaScript-style generator functions or Python's yield keyword. A common way to model generator behavior is with a channel and a goroutine.

The goroutine computes factorial values and sends them through the channel one at a time. After all values have been produced, the channel is closed.

The logic for computing factorials is identical to the Python solution. The only difference is the mechanism used to stream values to the caller.

Worked Examples

Example 1: n = 5

Initial state:

Variable	Value
factorial_value	1

Iteration	Number	factorial_value After Update	Yielded Value
1	1	1 × 1 = 1	1
2	2	1 × 2 = 2	2
3	3	2 × 3 = 6	6
4	4	6 × 4 = 24	24
5	5	24 × 5 = 120	120

Generated sequence:

[1, 2, 6, 24, 120]

Example 2: n = 2

Initial state:

Variable	Value
factorial_value	1

Iteration	Number	factorial_value After Update	Yielded Value
1	1	1	1
2	2	2	2

Generated sequence:

[1, 2]

Example 3: n = 0

The special case is triggered immediately.

Step	Action
1	Yield 1
2	Return

Generated sequence:

[1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One multiplication and one yield per value generated
Space	O(1)	Only a few variables are maintained regardless of n

The generator computes each factorial exactly once. Since there are n factorial values to generate, the total work is proportional to n. Aside from the output stream itself, only a single running factorial variable is stored, resulting in constant auxiliary space usage.

Test Cases

from typing import Generator

class Solution:
    def factorial(self, n: int) -> Generator[int, None, None]:
        if n == 0:
            yield 1
            return

        factorial_value = 1

        for number in range(1, n + 1):
            factorial_value *= number
            yield factorial_value

sol = Solution()

assert list(sol.factorial(0)) == [1]  # special case: 0!
assert list(sol.factorial(1)) == [1]  # smallest positive input
assert list(sol.factorial(2)) == [1, 2]  # example 2
assert list(sol.factorial(3)) == [1, 2, 6]  # first few factorials
assert list(sol.factorial(5)) == [1, 2, 6, 24, 120]  # example 1
assert list(sol.factorial(6)) == [1, 2, 6, 24, 120, 720]  # additional progression
assert list(sol.factorial(10))[-1] == 3628800  # larger factorial
assert list(sol.factorial(18))[-1] == 6402373705728000  # upper constraint boundary

Test Summary

Test	Why
n = 0	Validates the special definition of 0!
n = 1	Smallest positive input
n = 2	Confirms basic sequence generation
n = 3	Verifies factorial recurrence
n = 5	Matches the provided example
n = 6	Tests continued factorial growth
n = 10	Checks larger values
n = 18	Validates behavior at the maximum constraint

Edge Cases

Edge Case 1: n = 0

This is the most important special case in the problem. A naive loop from 1 to n would execute zero iterations and produce no output. However, the mathematical definition explicitly states that 0! = 1. The implementation handles this by checking n == 0 before entering the loop and yielding 1 immediately.

Edge Case 2: n = 1

When n = 1, the sequence contains exactly one value. Some implementations accidentally yield both 0! and 1!, producing [1, 1]. The required output contains only the factorials up to n, which means the correct sequence is simply [1]. The loop-based implementation naturally produces this result.

Edge Case 3: Maximum Input n = 18

Factorials grow very quickly. By the time we reach 18!, the value is 6402373705728000. An implementation that uses inappropriate numeric types could overflow. The problem guarantees that inputs remain within a range where the expected environment can safely represent the result. The algorithm computes the value incrementally and correctly handles the maximum allowed input.

Edge Case 4: Consecutive Factorials

A common mistake is recomputing factorials independently or using incorrect multiplication order, leading to skipped or duplicated values. Because the implementation maintains a running factorial and updates it using the recurrence i! = (i - 1)! × i, every yielded value is guaranteed to be the next factorial in sequence.