Factorial Generator - Video Solutions

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.