Given Q[] queries where each query consists of an integer N, the task is to find the product of first N factorials for each of the query. Since the result could be large, compute it modulo 109 + 7.
Examples:
Input: Q[] = {4, 5}
Output:
288
34560
Query 1: 1! * 2! * 3! * 4! = 1 * 2 * 6 * 24 = 288
Query 2: 1! * 2! * 3! * 4! * 5! = 1 * 2 * 6 * 24 * 120 = 34560
Input: Q[] = {500, 1000, 7890}
Output:
976141892
560688561
793351288
Approach: Create two arrays result[] and fact[] where fact[i] will store the factorial of i and result[i] will store the product of first i factorial.
Initialise fact[0] = 1 and result[0] = 1. Now for the rest of the values, the recurrence relation will be:
fact[i] = fact[i – 1] * i
result[i] = result[i – 1] * fact[i]
Now, each query can be answered using the result[] array generated.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long#define MAX 1000000const ll MOD = 1e9 + 7;// Declare result array globallyll result[MAX + 1];ll fact[MAX + 1];// Function to precompute the product// of factorials upto MAXvoid preCompute(){ // Initialize base condition if n = 0 // then factorial of 0 is equal to 1 // and answer for n = 0 is 1 fact[0] = 1; result[0] = 1; // Iterate loop from 1 to MAX for (int i = 1; i <= MAX; i++) { // factorial(i) = factorial(i - 1) * i fact[i] = ((fact[i - 1] % MOD) * i) % MOD; // Result for current n is equal to result[i-1] // multiplied by the factorial of i result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD; }}// Function to perform the queriesvoid performQueries(int q[], int n){ // Precomputing the result till MAX preCompute(); // Perform queries for (int i = 0; i < n; i++) cout << result[q[i]] << "\n";}// Driver codeint main(){ int q[] = { 4, 5 }; int n = sizeof(q) / sizeof(q[0]); performQueries(q, n); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{static int MAX = 1000000;static int MOD = 10000007;// Declare result array globallystatic int []result = new int [MAX + 1];static int []fact = new int [MAX + 1];// Function to precompute the product// of factorials upto MAXstatic void preCompute(){ // Initialize base condition if n = 0 // then factorial of 0 is equal to 1 // and answer for n = 0 is 1 fact[0] = 1; result[0] = 1; // Iterate loop from 1 to MAX for (int i = 1; i <= MAX; i++) { // factorial(i) = factorial(i - 1) * i fact[i] = ((fact[i - 1] % MOD) * i) % MOD; // Result for current n is equal to result[i-1] // multiplied by the factorial of i result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD; }}// Function to perform the queriesstatic void performQueries(int q[], int n){ // Precomputing the result till MAX preCompute(); // Perform queries for (int i = 0; i < n; i++) System.out.println (result[q[i]]);}// Driver codepublic static void main (String[] args) { int q[] = { 4, 5 }; int n = q.length; performQueries(q, n);}}// This code is contributed by tushil. |
Python3
# Python3 implementation of the approachMAX = 1000000MOD = 10**9 + 7# Declare result array globallyresult = [0 for i in range(MAX + 1)]fact = [0 for i in range(MAX + 1)]# Function to precompute the product# of factorials upto MAXdef preCompute(): # Initialize base condition if n = 0 # then factorial of 0 is equal to 1 # and answer for n = 0 is 1 fact[0] = 1 result[0] = 1 # Iterate loop from 1 to MAX for i in range(1, MAX + 1): # factorial(i) = factorial(i - 1) * i fact[i] = ((fact[i - 1] % MOD) * i) % MOD # Result for current n is # equal to result[i-1] # multiplied by the factorial of i result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD# Function to perform the queriesdef performQueries(q, n): # Precomputing the result tiMAX preCompute() # Perform queries for i in range(n): print(result[q[i]])# Driver codeq = [4, 5]n = len(q)performQueries(q, n)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System;class GFG{static int MAX = 1000000;static int MOD = 10000007;// Declare result array globallystatic int []result = new int [MAX + 1];static int []fact = new int [MAX + 1];// Function to precompute the product// of factorials upto MAXstatic void preCompute(){ // Initialize base condition if n = 0 // then factorial of 0 is equal to 1 // and answer for n = 0 is 1 fact[0] = 1; result[0] = 1; // Iterate loop from 1 to MAX for (int i = 1; i <= MAX; i++) { // factorial(i) = factorial(i - 1) * i fact[i] = ((fact[i - 1] % MOD) * i) % MOD; // Result for current n is equal to result[i-1] // multiplied by the factorial of i result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD; }}// Function to perform the queriesstatic void performQueries(int []q, int n){ // Precomputing the result till MAX preCompute(); // Perform queries for (int i = 0; i < n; i++) Console.WriteLine(result[q[i]]);}// Driver codepublic static void Main (String[] args) { int []q = { 4, 5 }; int n = q.Length; performQueries(q, n);}} // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach let MAX = 1000000; let MOD = 10000007; // Declare result array globally let result = new Array(MAX + 1); result.fill(0); let fact = new Array(MAX + 1); fact.fill(0); // Function to precompute the product // of factorials upto MAX function preCompute() { // Initialize base condition if n = 0 // then factorial of 0 is equal to 1 // and answer for n = 0 is 1 fact[0] = 1; result[0] = 1; // Iterate loop from 1 to MAX for (let i = 1; i <= MAX; i++) { // factorial(i) = factorial(i - 1) * i fact[i] = ((fact[i - 1] % MOD) * i) % MOD; // Result for current n is equal to result[i-1] // multiplied by the factorial of i result[i] = ((result[i - 1] % MOD) * (fact[i] % MOD)) % MOD; } } // Function to perform the queries function performQueries(q, n) { // Precomputing the result till MAX preCompute(); // Perform queries for (let i = 0; i < n; i++) document.write(result[q[i]] + "</br>"); } let q = [ 4, 5 ]; let n = q.length; performQueries(q, n); </script> |
Output:
288 34560
Time Complexity: O(MAX)
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
