Problem

Write a generator function that takes an integer n as an argument and returns a generator object which yields the factorial sequence.

The factorial sequence is defined by the relation `n! = n * (n-1) * (n-2)

  • … * 2 * 1​​​.`

The factorial of 0 is defined as 1.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input: n = 5
Output: [1,2,6,24,120]
Explanation: 
const gen = factorial(5)
gen.next().value // 1
gen.next().value // 2
gen.next().value // 6
gen.next().value // 24
gen.next().value // 120

Example 2:

1
2
3
4
5
6

Input: n = 2
Output: [1,2]
Explanation: 
const gen = factorial(2) 
gen.next().value // 1 
gen.next().value // 2

Example 3:

1
2
3
4
5

Input: n = 0
Output: [1]
Explanation: 
const gen = factorial(0) 
gen.next().value // 1

Constraints:

  • 0 <= n <= 18

Solution

Method 1 – Iterative Generator

Intuition

A factorial sequence is a cumulative product sequence. We can yield each factorial by multiplying the previous result by the next integer, starting from 1.

Approach

  1. Initialize a variable ans to 1.
  2. For each integer i from 1 to n:
    • Multiply ans by i.
    • Yield ans.
  3. The generator yields the factorial sequence up to n!.

Code

1
2
3
4
5
6
7

function* factorial(n) {
    let ans = 1;
    for (let i = 1; i <= n; i++) {
        ans *= i;
        yield ans;
    }
}
1
2
3
4
5
6
7

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

Complexity

  • ⏰ Time complexity: O(n), since we compute each factorial up to n.
  • 🧺 Space complexity: O(1), only a constant amount of space is used for variables.