In competitive programming, we often encounter the word modulo where we are asked to find out the answer in modulo as the answer can be huge, so we need to print out ‘modulo P’.
To find the factorial modulo, we must first compute ‘N!’ and then calculate ‘N! % P’. This solution works well when the value of ‘N!’ is very small. The value of ‘N! % P’ is usually wanted for larger values of ‘N’ when ‘N!’ cannot fit into a variable and reasons an overflow. Therefore, calculation of ‘N!’ and then performing modulation is not a great idea to proceed as for slightly larger values of ‘N’ and ‘R’, there will always be an overflow where ‘N’ denotes the total number of items and ‘R’ represents the number of items chosen at a time, and ‘P’ denotes the prime number.
CREDITS: GIPHY
Working of factorial modulo
Complex formulas modulo some prime ‘P’, comprising factorials in both the numerator and denominator, such as those found in the formula for Binomial coefficients we come around often. We consider this situation when ‘P’ is relatively small.
Only when factorials exist in both the numerator and denominator of fractions, this problem make sense. Otherwise, the value of ‘P!’ and succeeding terms will be 0. In fractions, however, the factors of ‘P’ can be cancelled, resulting in a non-zero modulo ‘P’ statement.
Hence, we have the challenge to calculate ‘N! mod P’ without considering all of the numerous factors of ‘P’ that exist in the factorial. Let us write N’s prime factorization while removing all the ‘P’ factors and computing the product modulo ‘P’. This updated factorial is denoted by ‘N! % P’.
Sieve Method
The Sieve Method
Here, the solution is to find all the primes smaller than ‘N’ using the sieve method for every prime ‘P’ while searching the highest power of it that divides N!.
The greatest possible power if a prime ‘P’ which divides ‘N’ is,
[N / P] + [N / P2] + [N / P3] + … + 0
We can write every integer in the form of a multiplication of the powers of the prime numbers. Therefore,
N! = P1K1 * P2K2 * P3K3 * … where,
P1, P2 and P3 ... are prime numbers and
K1, K2 and K3 are integers that are greater than or equal to 1.
Example:We have an integer ‘N’ and ‘P’ as a prime number. We need to find the largest number, ‘X’, such that PX (P to the power of X) divides factorial ‘N’ .
‘N’ = 7
‘P’ = 3
We know, 7! = 5040
The highest power of the prime number ‘P’ that can help ‘P’ to divide 5040 completely is 2.
32 divides 7!.
Hence, X = 2
Code:-
#include <bits/stdc++.h> usingnamespacestd;
/* Function returning the highest power of factorial modulo P that divides N! */ inthighestPower(int N, int P){ int result = 0;
/* Calculating the result, result = N/P + N/(P^2) + N/(P^3) + ... */ while(N){ N /= P; result += N; } return result; }
// Function for modular exponentiation which will return (X^Y) % P intmodularExp(int X, int Y, int P){ int ans = 1;
// To update the 'X' value if it is equal or more than P X = X % P; while(Y > 0){
// If the 'Y' value is odd, we will multiply X with the result if(Y & 1) ans = (ans * X) % P;
// When the 'Y' value is even Y = Y >> 1; X = (X * X) % P; } return ans; }
// Function for factorial modulo N! % P intfactorialMod(int N, int P){ if(N >= P) return0;
int ans = 1;
// Using sieve method to find out the prime numbers smaller than N bool primeNo[N + 1]; memset(primeNo, 1, sizeof(primeNo)); for(int i = 2; i * i <= N; i++){ if(primeNo[i]){ for(int j = 2 * i; j <= N; j += i) primeNo[j] = 0; } }
// To consider all the primes found by the Sieve method for(int i = 2; i <= N; i++){ if(primeNo[i]){
// To find the highest power of prime no. 'i' that divides N int s = highestPower(N, i);
// We will multiply the result with (i ^ s) % P ans = (ans * modularExp(i, s, P)) % P; } } return ans; }
// Main program intmain(){ int N = 6; int P = 11; cout << "The result of " << N << "! % " << P << " is " << factorialMod(N, P) << "."; return0; }
To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1).
This theorem states that natural number ‘P’ > 1 is a prime number if and only if,
(P - 1) ! 𝞝 -1 % P, or
(P - 1) ! 𝞝 (P - 1) % P
If N >= P, then N! % P = 0.
This method is possible when P is relatively close to the input number N.
Example:28! = 1
Code:-
#include <bits/stdc++.h> usingnamespacestd;
// Function for modular exponentiation which will return (X^Y) % P intmodularExp(int X, unsignedint Y, int P){ int ans = 1;
// To update the 'X' value if it is equal or more than P X = X % P; while(Y > 0){
// If the 'Y' value is odd, we will multiply X with the result if(Y & 1) ans = (ans * X) % P;
// When the 'Y' value is even Y = Y >> 1; X = (X * X) % P; } return ans; } /* Function returning the modular inverse of modulo P assuming P is prime( using Fermat's method) */ intinverseMod(int N, int P){ return modularExp(N, P - 2, P); }
// Function for factorial modulo N! % P intfactorialMod(int N, int P){ if(N >= P) return0; // To initialise the result as (P - 1)! , i.e., -1 or (P - 1) int ans = (P - 1);
// To multiply the modulo inverse of all the no.s from (N + 1) for(int i = N + 1; i < P; i++){ ans = (ans * inverseMod(i, P)) % P; } return ans; }
// Main program intmain(){ int N = 6; int P = 11; cout << "The result of " << N << "! % " << P << " is " << factorialMod(N, P) << "."; return0; }
Output:
The result of 6! % 11 is 5.
Time Complexity:
The time complexity for this approach will be O((P - N)* log N).
As, (P - 1)! = (P - 1) (P - 2) (P - 3) … 3 x 2 x 1
= (P - N) x (log N), where ’P’ is the prime number.
Space Complexity:
To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1).
Algorithm for factorial modulo using Brute-force Approach
Simple Method
The method is to multiply the result one by one with ‘i’ under the modulo ‘P’. Therefore, the value of the result does not exceed ‘P’ before the next iteration.
Example: ‘N’ = 5
‘P’ = 13
‘N! % P’ = 120 % 13 = 3
The concept here is to apply the brute force approach.
We can consider computing N! first and then move on to find modulo P. But this could cause the overflow hassle because N! might be a large number. So, computing N! and then applying % is not a good idea.
We can conquer this hassle via using the modulo operator in each iteration. In other words, we can multiply one by one with ‘i’ under modulo ‘P’.
We will first declare a variable ‘ans’ = 1.
We then run a loop from ‘i’ = 1 to ‘i’ <= N, at each iteration do:
ans = (ans * i) % P
We will then return the ‘ans’.
As we know,
(A * B) % M == ((A % M) * (B % M)) % M
For the factorial,
N! = 1 * 2 * 3 * … * (N - 1) * N
Therefore, we get
N! % M = (((((((1 * 2) % M) * 3) % M) * … * N -1) % M) * N) % M
Implementation of factorial modulo in C++
#include <bits/stdc++.h> usingnamespacestd;
// Computes the value of N! % P intfactorialModulo(int N, int P){ if(N >= P){ return0; } int ans = 1;
for(int i = 1; i <= N; i++){ ans = (ans * i) % P; } return ans; }
// Driver code intmain(){ int N = 6; int P = 11; cout << "The result of " << N << "! % " << P << " is " <<factorialModulo(N, P)<<"."; return0; }
OUTPUT-
The result of 6! % 11 is 5.
Time Complexity
The time complexity for this problem is O(N). As we are using one single iteration from 1 to ‘N’.
Space Complexity
The space complexity for this algorithm is O(1) as the space required by the above algorithm to process the data is constant.
Frequently Asked Questions
What is meant by ‘ print in modulo 109 + 7 ’?
(109 + 7) is the first ten-digit prime number, and printing the answer in modulo ensures that the answer fits in the maximum value that our system can store, which is generally consistent with the question setter's code or case tester's code. This also makes sure that it prevents ‘integer overflow’ during the compilation process as it takes significant effort to store and process actual huge value.
What is the need for modulo?
We need modulo to avoid ‘integer overflow’ as in C / C++, the largest integer data type is of 64 bit (unsigned long long int), which can only handle data from 0 to 264 - 1.
In several problems, to compute the end result, modulo inverse is wanted, and (109 + 7) is the number that helps in this case as it is prime and large enough or else modular inverse strategies can also additionally fail in some situations.
List out some properties of modulo.
Some properties of modulo are following:-
(A + B) % C = ((A % C) + (B % C)) % C
(A * B) % C = ((A % C) * (B % C)) % C
(A - B) % C = ((A % C) - (B % C)) % C
(A / B) % C ≠ ((A % C) / (B % C)) % C
(A / B) % C = (A * ( B-1 )) % C
Note: The result of (A % B) is always less than B.
What is Wilson’s theorem?
This theorem states that a natural number N > 1 is a prime number if and only if the product of all the positive numbers less than N is one less than the multiple of N.
(N - 1)! = 1 * 2 * 3 * .... * (N - 1) satisfies
(N - 1)! 𝞝 -1 (mod N)
Here, ‘N’ is a prime number.
Or, we can say, any number ‘N’ is a prime number iff (N - 1)! + 1 is divisible by N.
What is the multiplicity of P?
We need VP, the multiplicity of P, for computing the binomial coefficient modulo P.
intmultiplicityFactorial(int N, int P){ int count = 0; do { N /= P; count += N; } while(N); return count; }
The idea behind this is to remove all the elements that do not contain the factor P. This leaves [N / P] elements remaining. If we remove the factor P from each, we get the product as 1 * 2 * 3 * … * [N / P] = [N / P]! using the recursion process.
Key Takeaways
In this blog, we learned about implementing factorial modulo, the working of factorial modulo and some basic concepts. If you want to know more about Modulo Arithmetic then you can visit modulo arithmetic for a sound knowledge of concepts of factorial modulo.
If you want to practice more problems then you can visit Coding Ninjas Studio to understand the working concept of factorial modulo.
38+ registered 