Given a number N. Find the product of first N factorials modulo 1000000007.
Constraints: 1 ≤ N ≤ 1e6
Examples:
Input : 3 Output : 12 Explanation: 1! * 2! * 3! = 12 mod (1e9 + 7) = 12 Input : 5 Output : 34560
Prerequisites: Modular Multiplication
Approach: The basic idea behind solving this problem is to just consider the problem of overflow during the multiplication of such large numbers i.e. factorials. Hence, it needs to be addressed by multiplying recursively to overcome the difficulty of overflow. Moreover, we have to take modulus at every step while computing factorials iteratively and modular multiplication.
facti = facti-1 * i where facti is the factorial of ith number prodi = prodi-1 * facti where prodi is the product of first i factorials
To find the product of two large numbers under modulo, we use the same approach as exponentiation under modulo… In the multiplication function, we use + instead of *.
Steps to solve the problem:
- Define a function named mulmod() that takes three arguments a, b, and mod.
- Inside mulmod(), initialize res to 0.
- Compute a = a % mod.
- While b > 0, perform the following operations:
- If b % 2 == 1, add a to res modulo mod.
- Multiply a by 2 and compute a = a % mod.
- Divide b by 2 and discard the remainder. Return res % mod.
- Define a function named findProduct() that takes a single argument N.
- Inside findProduct(), initialize product and fact to 1.
- Set MOD = 1e9 + 7.
- For i in the range 1 to N, perform the following operations:
- Compute fact as the product of fact and i modulo MOD, i.e., fact = mulmod(fact, i, MOD)
- Compute product as the product of product and fact modulo MOD, i.e., product = mulmod(product, fact, MOD).
- If product is zero, return 0.
- Return product
Below is the implementation of the above approach.
C++
// CPP Program to find the// product of first N factorials#include <bits/stdc++.h>using namespace std;// To compute (a * b) % MODlong long int mulmod(long long int a, long long int b, long long int mod){ long long int res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod;}// This function computes factorials and// product by using above function i.e.// modular multiplicationlong long int findProduct(long long int N){ // Initialize product and fact with 1 long long int product = 1, fact = 1; long long int MOD = 1e9 + 7; for (int i = 1; i <= N; i++) { // ith factorial fact = mulmod(fact, i, MOD); // product of first i factorials product = mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product;}// Driver Code to Test above functionsint main(){ long long int N = 3; cout << findProduct(N) << endl; N = 5; cout << findProduct(N) << endl; return 0;} |
Java
// Java Program to find the// product of first N factorialsclass GFG{// To compute (a * b) % MODstatic double mulmod(long a, long b, long mod){ long res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod;}// This function computes factorials and// product by using above function i.e.// modular multiplicationstatic long findProduct(long N){ // Initialize product and fact with 1 long product = 1, fact = 1; long MOD = (long)(1e9 + 7); for (int i = 1; i <= N; i++) { // ith factorial fact = (long)mulmod(fact, i, MOD); // product of first i factorials product = (long)mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product;}// Driver Code to Test above functionspublic static void main(String[] args){ long N = 3; System.out.println(findProduct(N)); N = 5; System.out.println(findProduct(N));}}// this Code is contributed by mits |
Python3
# Python Program to find the# product of first N factorials# To compute (a * b) % MODdef mulmod(a, b, mod): res = 0 # Initialize result a = a % mod while (b > 0): # If b is odd, add 'a' to result if (b % 2 == 1): res = (res + a) % mod # Multiply 'a' with 2 a = (a * 2) % mod # Divide b by 2 b //= 2 # Return result return res % mod# This function computes factorials and# product by using above function i.e.# modular multiplicationdef findProduct(N): # Initialize product and fact with 1 product = 1; fact = 1 MOD = 1e9 + 7 for i in range(1, N+1): # ith factorial fact = mulmod(fact, i, MOD) # product of first i factorials product = mulmod(product, fact, MOD) # If at any iteration, product becomes # divisible by MOD, simply return 0 if not product: return 0 return int(product)# Driver Code to Test above functionsN = 3print(findProduct(N))N = 5print(findProduct(N))# This code is contributed by Ansu Kumari |
C#
// C# Program to find the// product of first N factorialsusing System;public class GFG{ // To compute (a * b) % MODstatic double mulmod(long a, long b, long mod){ long res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod;}// This function computes factorials and// product by using above function i.e.// modular multiplicationstatic long findProduct(long N){ // Initialize product and fact with 1 long product = 1, fact = 1; long MOD = (long)(1e9 + 7); for (int i = 1; i <= N; i++) { // ith factorial fact = (long)mulmod(fact, i, MOD); // product of first i factorials product = (long)mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product;}// Driver Code to Test above functions static public void Main (){ long N = 3; Console.WriteLine(findProduct(N)); N = 5; Console.WriteLine(findProduct(N));}}//This Code is contributed by ajit. |
PHP
<?php// PHP Program to find the// product of first N factorials// To compute (a * b) % MODfunction mulmod($a, $b, $mod){ $res = 0; // Initialize result $a = $a % $mod; while ($b > 0) { // If b is odd, add 'a' to result if ($b % 2 == 1) $res = ($res + $a) % $mod; // Multiply 'a' with 2 $a = ($a * 2) % $mod; // Divide b by 2 $b /= 2; } // Return result return $res % $mod;}// This function computes factorials and// product by using above function i.e.// modular multiplicationfunction findProduct($N){ // Initialize product and fact with 1 $product = 1; $fact = 1; $MOD = 1000000000; for ($i = 1; $i <= $N; $i++) { // ith factorial $fact = mulmod($fact, $i, $MOD); // product of first i factorials $product = mulmod($product, $fact, $MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if ($product == 0) return 0; } return $product;}// Driver Code$N = 3;echo findProduct($N),"\n";$N = 5;echo findProduct($N),"\n";// This code is contributed by ajit?> |
Javascript
<script> // Javascript Program to find the // product of first N factorials // To compute (a * b) % MOD function mulmod(a, b, mod) { let res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b = parseInt(b / 2, 10); } // Return result return res % mod; } // This function computes factorials and // product by using above function i.e. // modular multiplication function findProduct(N) { // Initialize product and fact with 1 let product = 1, fact = 1; let MOD = (1e9 + 7); for (let i = 1; i <= N; i++) { // ith factorial fact = mulmod(fact, i, MOD); // product of first i factorials product = mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product; } let N = 3; document.write(findProduct(N) + "</br>"); N = 5; document.write(findProduct(N));</script> |
Output:
12 34560
Time Complexity: O(N * logN), where O(log N) is the time complexity of modular multiplication.
Auxiliary Space: O(1) because it is using constant space for variables
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!
