# Modular Factorial Of Multiple Numbers

Using Dynamic Programming and generating Modular Factorial Array in Rust

## Naive Approach

In the previous articles, we discussed how to find factorial of a number and how to find factorial of very large numbers using Modular Arithmetic.

As we have already seen in these article, the **Time Complexity for calculating the factorial of each number is O( n )**
So, if we find the factorial of m numbers, clearly the time complexity will be **O( m × n )** , where n is the largest number among m numbers.

Now, let's see a code to demonstrate this. We will use the Iterative function used in find factorial of very large numbers using Modular Arithmetic.

Program

use std::io::stdin;fn factorial(number : i128, divisor: i128) -> i128 {let mut factorial: i128 = 1;for i in 1..(number + 1) {factorial *= i;factorial %= divisor;}return factorial;}pub fn main() {println!("Enter array : ");// Read Array of Integerslet mut input = String::new();stdin().read_line(&mut input).unwrap();let arr: Vec<i128> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();// For all number in array, find and print factorial, modulo 1000000007// You can replace 1000000007 with any number you like// Also, I am using borrowing, so that we can reuse the array again laterfor number in &arr {let factorial = factorial(*number, 1000000007);println!("Factorial of {} is : {}", number, factorial);}}

**Output**

Enter array :

12 13 14 15 16

Factorial of 12 is : 479001600

Factorial of 13 is : 227020758

Factorial of 14 is : 178290591

Factorial of 15 is : 674358851

Factorial of 16 is : 789741546

**Time Complexity : O( m×n )**

**Space Complexity : O(1)**

## Overlapping Sub-problems

In the above example, we are calculating the factorial of array [12, 13, 14, 15, 16].

For this, we are first calculating 12!, then again 12! and multiply it with 13, to get 13!, then again calculate 13! and multiply with 14 to get 14! and so on. It is depicted by picture below

So, instead of calculating factorial of 12 5 times, we calculate it once and store it, and again access it, when needed

## Tabulation Method ( Dynamic Programming )

In Tabulation method, we simply create an array, in which index represents the factorial of number. So,

- factorial_array[0] = 0! = 1
- factorial_array[1] = 1! = 1
- factorial_array[2] = 2! = 2
- factorial_array[3] = 3! = 6

and so on.

We can easily use it in the code, any way we like.

If we already have factorial array, then finding factorial of any number is done in **Time Complexity = O( 1 )**, like in above permutation, it takes constant time complexity !

Following function generates factorial array, ** which contains factorial of all numbers upto given maximum number**. It also receives a divisor, to store modulo of number, instead of given number itself

### Function to generate factorial array

fn generate_factorial_array(max_number : i128, divisor : i128) -> Vec<i128>{// This function generates and returns an array,// with index representing factorial of the number// Convert i128 to usize, so that we can access array slices in rustlet max_number : usize = max_number as usize;// Initially set every element to 0let mut factorial_array : Vec<i128> = vec![0; max_number+1];factorial_array[0] = 1;factorial_array[1] = 1;// Set next factorial to i * previous factorial % divisorfor i in 2..(max_number + 1) {factorial_array[i] = (factorial_array[i-1] * (i as i128)) % divisor;}return factorial_array}

### With driver code

use std::io::stdin;fn generate_factorial_array(max_number : i128, divisor : i128) -> Vec<i128>{// This function generates and returns an array, with index representing factorial of the number// Convert i128 to usize, so that we can access array slices in rustlet max_number : usize = max_number as usize;// Initially set every element to 0let mut factorial_array : Vec<i128> = vec![0; max_number+1];factorial_array[0] = 1;factorial_array[1] = 1;// Set next factorial to i * previous factorial % divisorfor i in 2..(max_number + 1) {factorial_array[i] = (factorial_array[i-1] * (i as i128)) % divisor;}return factorial_array}pub fn main() {// Read Array of Integersprintln!("Enter array : ");let mut input = String::new();stdin().read_line(&mut input).unwrap();let arr: Vec<i128> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();// Read Divisorprintln!("Enter divisor : ");input.clear();stdin().read_line(&mut input).unwrap();let divisor : i128 = input.trim().parse().unwrap();// Find Maximum number in the arraylet mut max_number: i128 = arr[0];for i in &arr {if *i > max_number {max_number = *i;}}// Now, generate the factorial array for the maximum number and divisorlet factorial_array = generate_factorial_array(max_number, divisor);// Now, print the factorial of each element in array, using above generated factorial array.for i in &arr {print!(" {} ", factorial_array[*i as usize])}}

**Output**

Enter array :

12 13 14 15 16

Factorial of 12 is : 479001600

Factorial of 13 is : 227020758

Factorial of 14 is : 178290591

Factorial of 15 is : 674358851

Factorial of 16 is : 789741546

**Time Complexity : O( n + m )**

**Space Complexity : O( n )**

**Note :** Complexity O( m+n ) signifies that time complexity is maximum O( m ) and O ( n ). Hence, it is **Linear Time and Space Complexity**

## Conclusion

If we find the factorial of multiple numbers one by one, it may take time O( m × n ) or quadratic time complexity. But, we can calculate it in linear space and time complexity using Dynamic Programming and generating Factorial Array.

Here is function for easy access

fn generate_factorial_array(max_number : i128, divisor : i128) -> Vec<i128>{let max_number : usize = max_number as usize;let mut factorial_array : Vec<i128> = vec![1; max_number+1];for i in 2..(max_number + 1) {factorial_array[i] = (factorial_array[i-1] * (i as i128)) % divisor; }return factorial_array}

Reading these articles, you now know enough about factorials and how to make efficient factorial programs in Rust.

Now, we should see the Permutation and combination and learn how to apply the concept of Factorial.

**Thank You**