2803. Factorial Generator
Problem Description
The task is to write a generator function that produces a sequence of factorials for a given integer n
. A factorial of a non-negative integer n
is the product of all positive integers less than or equal to n
. It's denoted as n!
and is calculated as n! = n * (n - 1) * (n - 2) * ... * 2 * 1
with the special case of 0!
equaling 1
. The challenge here involves creating a function that, when invoked, generates each value in the factorial sequence up to n
on-demand, rather than computing them all at once.
Intuition
To solve this problem, we use a generator in TypeScript, which allows us to yield values one at a time whenever the generator's next()
method is called. This fits our goal perfectly, as we want to produce factorial values in a sequence, without computing them all upfront.
The intuition behind the solution is to maintain a running product that starts at 1 (0!
is 1). As we iterate from 1 to n
, we multiply the running product by the current number i
to get i!
, and then we yield this result. This way, we get each factorial value in turnāfrom 1!
to n!
āand any code using this generator can retrieve the next value in the factorial sequence whenever required without calculating the entire sequence ahead of time.
With this approach, we can efficiently generate factorial values for each step without redundant calculations, using the previously computed value as the foundation for the next.
Solution Approach
To implement the solution, a Generator function in TypeScript is used, identified by the function*
syntax and enabling the yield
keyword within its body. Here's the step-by-step approach used in the provided solution:
-
The generator checks if the input
n
is 0. Since the factorial of 0 is defined as 1, it yields1
immediately.if (n === 0) { yield 1; }
-
We declare a variable
ans
to keep track of the running product of the series, initializing it to 1 (0!
). -
We use a
for
loop to iterate from 1 ton
. On each iteration, we updateans
by multiplying it by the current numberi
, which effectively calculatesi!
.for (let i = 1; i <= n; ++i) { ans *= i; yield ans; }
-
During each iteration of the loop, after updating
ans
to hold the factorial ofi
, we useyield
to produce the current value ofans
. This allows the caller to retrieve the values of the factorial sequence one by one on-demand.
The algorithm efficiently computes each factorial value in the sequence by building on the previous value, thus avoiding recomputation of factorials. This is a fundamental principle in dynamic programming, although the solution does not store all previously computed values, just the most recent product.
Data structures:
- The generator itself serves as a custom iterable data structure, allowing the caller of this function to receive factorial values incrementally.
Patterns used:
- Generator Pattern - Allows the function to yield multiple values over time, rather than computing them all at once and returning them.
- Iteration - Uses a simple loop to traverse from 1 to
n
, aligning with the sequence of factorial calculation. - In-place Computation - Updates the
ans
variable in each iteration which holds the latest factorial value.
Overall, this approach maximizes efficiency minimizing both time and space complexity, as it calculates each factorial product when needed without storing all results or performing redundant calculations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example where n = 4
. The goal is to generate the sequence of factorials for the numbers 0
through 4
, which are 1
, 1
, 2
, 6
, and 24
, respectively.
-
The generator checks if
n
is0
. In our case, sincen
is4
, it doesn't yield1
immediately and moves on to the next steps. -
A variable
ans
is declared and initialized to1
, which represents the factorial for0
(0!
). -
We start a loop from
1
up to and includingn
, which is4
in our case. In each iteration of the loop,ans
would be updated as follows:- First Iteration (
i = 1
):ans *= i
āans = 1 * 1
- The generator yields the current value of
ans
, which is1
.
- Second Iteration (
i = 2
):ans *= i
āans = 1 * 2
- The generator yields the current value of
ans
, which is2
.
- Third Iteration (
i = 3
):ans *= i
āans = 2 * 3
- The generator yields the current value of
ans
, which is6
.
- Fourth Iteration (
i = 4
):ans *= i
āans = 6 * 4
- The generator yields the current value of
ans
, which is24
.
- First Iteration (
-
During each iteration, after
ans
is updated to hold the factorial ofi
,yield
is used to produce the currentans
value. This allows the caller to get the factorial values one at a time on-demand.
Assuming the calling code continually invokes the generator's next()
method after each value is yielded, it would receive the sequence of factorial values one by one:
next()
ā1
(which is1!
)next()
ā2
(which is2!
)next()
ā6
(which is3!
)next()
ā24
(which is4!
)
In real-world usage, this can be very memory efficient, as we compute each factorial as needed without storing every single result. This method is particularly useful when working with very large sequences where memory consumption is a concern.
Solution Implementation
1# This generator function calculates factorial numbers up to n.
2# It yields each intermediate factorial result in the sequence.
3def factorial(n):
4 # Base case: the factorial of 0 is 1.
5 if n == 0:
6 yield 1
7
8 # Initialize the accumulator variable for the factorial calculation.
9 accumulator = 1
10
11 # Iterate from 1 to n, multiplying the accumulator by each number.
12 for i in range(1, n + 1):
13 accumulator *= i
14
15 # Yield the current result of the factorial up to i.
16 yield accumulator
17
18# Usage example:
19# Create an instance of the generator for the factorial of 2.
20generator = factorial(2)
21
22# Retrieve and print the first result from the generator, which is 1! = 1.
23print(next(generator)) # Outputs: 1
24
25# Retrieve and print the second result from the generator, which is 2! = 2.
26print(next(generator)) # Outputs: 2
27
1import java.util.Iterator;
2
3// This class represents an iterable sequence of factorial numbers up to a given n.
4public class FactorialSequence implements Iterable<Integer> {
5 private final int n;
6
7 // Constructor for the FactorialSequence class
8 public FactorialSequence(int n) {
9 this.n = n;
10 }
11
12 // Method to create and return an iterator over the factorial sequence.
13 @Override
14 public Iterator<Integer> iterator() {
15 return new Iterator<>() {
16 private int current = 0;
17 private int accumulator = 1;
18
19 // Checks if the next factorial number is available.
20 @Override
21 public boolean hasNext() {
22 return current <= n;
23 }
24
25 // Computes and returns the next factorial number.
26 @Override
27 public Integer next() {
28 if (current == 0 || current == 1) {
29 // Factorial of 0 or 1 is always 1.
30 current++;
31 return accumulator; // 1
32 } else {
33 accumulator *= current;
34 current++;
35 return accumulator;
36 }
37 }
38 };
39 }
40
41 // Usage example:
42 public static void main(String[] args) {
43 // Create an instance of the factorial sequence for the factorial of 2.
44 FactorialSequence sequence = new FactorialSequence(2);
45
46 // Retrieve and print results from the sequence using an iterator.
47 Iterator<Integer> iterator = sequence.iterator();
48
49 // Retrieve and print the first result from the sequence, which is 1! = 1.
50 System.out.println(iterator.next()); // Outputs: 1
51
52 // Retrieve and print the second result from the sequence, which is 2! = 2.
53 System.out.println(iterator.next()); // Outputs: 2
54 }
55}
56
1#include <iostream>
2#include <vector>
3
4// This class represents a 'generator' for factorial numbers up to 'n' using precomputation.
5class FactorialGenerator {
6private:
7 std::vector<int> factorials;
8 size_t currentIndex;
9
10public:
11 // Constructor that precalculates the factorials up to 'n'.
12 explicit FactorialGenerator(int n) : currentIndex(0) {
13 // Reserve space for the factorial results for optimization.
14 factorials.reserve(n + 1);
15
16 // Base case: the factorial of 0 is 1.
17 factorials.push_back(1);
18
19 // Compute the factorial of each number in the sequence up to 'n' and store the results.
20 int accumulator = 1;
21 for (int i = 1; i <= n; ++i) {
22 accumulator *= i;
23 factorials.push_back(accumulator);
24 }
25 }
26
27 // Function to get the next factorial in the sequence.
28 int next() {
29 // Check if there are more factorials to return.
30 if (currentIndex < factorials.size()) {
31 // Return the next factorial and increment the index.
32 return factorials[currentIndex++];
33 } else {
34 // If there are no more factorials, throw an exception or handle the case as desired.
35 throw std::out_of_range("No more factorials in the sequence.");
36 }
37 }
38
39 // Function to check if there are more factorials to be generated.
40 bool hasNext() const {
41 return currentIndex < factorials.size();
42 }
43};
44
45int main() {
46 // Usage example:
47 // Create an instance of the generator for factorial of 2.
48 FactorialGenerator generator(2);
49
50 // Retrieve and print the first result from the generator, which is 1! = 1.
51 if (generator.hasNext()) {
52 std::cout << generator.next() << std::endl; // Outputs: 1
53 }
54
55 // Retrieve and print the second result from the generator, which is 2! = 2.
56 if (generator.hasNext()) {
57 std::cout << generator.next() << std::endl; // Outputs: 2
58 }
59
60 return 0;
61}
62
1// This generator function calculates factorial numbers up to n.
2// It yields each intermediate factorial result in the sequence.
3function* factorial(n: number): Generator<number> {
4 // Base case: the factorial of 0 is 1.
5 if (n === 0) {
6 yield 1;
7 }
8
9 // Initialize the accumulator variable for the factorial calculation.
10 let accumulator = 1;
11
12 // Iterate from 1 to n, multiplying the accumulator by each number.
13 for (let i = 1; i <= n; ++i) {
14 accumulator *= i;
15
16 // Yield the current result of the factorial up to i.
17 yield accumulator;
18 }
19}
20
21// Usage example:
22// Create an instance of the generator (iterator) for factorial of 2.
23const generator = factorial(2);
24
25// Retrieve and print the first result from the generator, which is 1! = 1.
26console.log(generator.next().value); // Outputs: 1
27
28// Retrieve and print the second result from the generator, which is 2! = 2.
29console.log(generator.next().value); // Outputs: 2
30
Time and Space Complexity
The time complexity of this generator function is O(n)
. This is because the loop within the generator runs n
times, with each iteration involving a constant number of operations (a multiplication and a yield). Therefore, the overall number of operations linearly depends on the input n
.
The space complexity of the generator is O(1)
. This is because the space required by the generator does not grow with the input n
. It uses a fixed amount of space to store the local variables (ans
, i
) regardless of the size of n
. The fact that this function yields the factorial of n
in each iteration does not add to the space complexity because the generated values are not stored in memory; they are produced on-demand.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!