Skip to main content
Talentd

Factorial Generator - Solution & Explanation

EasyPremiumFree on FleetCode3 min read
Practice this problem

Problem Statement

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.

 

Example 1:

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:

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

Example 3:

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

 

Constraints:

  • 0 <= n <= 18

Approach Overview

Problem Overview: Factorial Generator asks you to produce factorial values sequentially for integers from 0 or 1 up to n. Instead of computing a single factorial, the goal is to generate each factorial in order efficiently.

Approach 1: Recompute Factorial Each Time (Brute Force) (Time: O(n^2), Space: O(1))

The straightforward method calculates the factorial for every number independently. For each i from 1 to n, iterate again from 1 to i and multiply the values to compute i!. This uses basic iteration and no extra data structures. The drawback is repeated work: computing 5! recalculates the entire multiplication chain even though 4! was already computed earlier. Total operations add up to 1 + 2 + 3 + ... + n, giving O(n^2) time complexity. Space usage remains O(1) since only a few variables are stored.

Approach 2: Running Factorial (Incremental Generator) (Time: O(n), Space: O(1))

The optimal solution keeps a running factorial value and updates it incrementally as numbers increase. Start with fact = 1. For each step i, compute the next factorial using fact = fact * i and emit or store the result. This works because factorials follow a simple recurrence: i! = (i-1)! * i. Instead of recomputing multiplications, each new value builds directly from the previous one.

This pattern is commonly implemented with an iterator or generator that yields each factorial as it's produced. Only one multiplication occurs per step, making the total runtime O(n). The algorithm stores only the current factorial and loop counter, so auxiliary space stays O(1). This incremental technique is typical in math problems and efficient sequence generation tasks.

Alternative Variant: Recursive Factorial Generation (Time: O(n), Space: O(n))

A recursive function can also compute factorials using n * factorial(n-1). While elegant, generating a sequence this way requires repeated recursive calls or memoization. Each call adds stack overhead, resulting in O(n) recursion depth and O(n) space due to the call stack. This method mainly demonstrates understanding of recursion rather than being the most practical implementation.

Recommended for interviews: Use the incremental running factorial approach. Interviewers expect you to recognize the recurrence relation and avoid redundant work. Starting with the brute force explanation shows baseline reasoning, but moving to the O(n) running product demonstrates algorithmic optimization and familiarity with efficient iteration patterns.

Solution

Code

TypeScript

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recompute Factorial Each TimeO(n^2)O(1)Conceptual baseline or when demonstrating the factorial definition directly
Running Factorial (Incremental)O(n)O(1)Best general solution for generating factorial sequence efficiently
Recursive Factorial GenerationO(n)O(n)Useful when demonstrating recursion concepts or mathematical definitions

Video Solution

3 Tips I’ve learned after 2000 hours of Leetcode • Top SWE • 616,521 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Factorial Generator easy or hard?
Factorial Generator is generally classified as an easy problem. It focuses on recognizing the factorial recurrence relation and implementing an efficient iterative solution with O(n) time complexity.
Factorial Generator Python/Java solution
In Python or Java, iterate from 1 to n and keep multiplying a running variable storing the current factorial. Append each result to a list or yield it from a generator. The algorithm runs in O(n) time and uses constant extra space.
How to solve Factorial Generator in O(n)?
Track the previous factorial and update it iteratively. Initialize fact = 1, then iterate from 1 to n and compute fact = fact * i at each step. Emit or store the value after each update. This ensures each factorial is calculated once.
What is the best approach for Factorial Generator?
The incremental running factorial approach is the most efficient. Maintain a variable storing the current factorial and update it using fact = fact * i for each step. This avoids recomputation and generates each factorial in O(1) additional work, resulting in O(n) total time and O(1) space.
Is Factorial Generator asked at Google/Amazon/Meta?
Factorial-style problems appear frequently in coding interviews as warm‑up questions or to test understanding of iteration, recursion, and mathematical sequences. Variants may show up in screening rounds at companies like Amazon or Google.
What data structure is used in Factorial Generator?
The problem typically does not require complex data structures. A simple integer variable to store the current factorial and a loop counter is enough. Some implementations use generators or iterators to yield results lazily.
What is the time complexity of Factorial Generator?
The optimal approach runs in O(n) time because each factorial value is derived from the previous one using a single multiplication. A naive brute force implementation that recomputes factorials for every number takes O(n^2) time.

Ready to solve this problem?

Practice Factorial Generator with our built-in code editor and test cases.

Practice on FleetCode