Last Updated: 26 Apr, 2021
Boring Factorials
Easy
Asked in company
You are given an integer ‘N’ and a prime number ‘P’. Your task is to find the N! modulo P.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first and only line of each test case contains two integers, ‘N’, and ‘P’ in that order, where N is the integer and P is a prime number.
Output Format :
For each test case, print the “N! % P”, as described in the problem statement.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^9
1 <= P <= 10^9
|N - P| <= 1000
Time Limit: 1 sec
Approaches
- The idea here is to use the brute force approach.
- One can think of computing the N! first and then find its modulo P. But this can lead to the overflow problem as the N! can be a very large number. So, computing N! and then using % is not a good idea.
- We can overcome this problem by using the modulo operator at each iteration. In other words, we multiply one by one with ‘i’ under modulo ‘P’.
- Declare a variable ans = 1.
- Run a loop from i = 1 to i <= N, in each iteration do:
- ans = (ans * i) % P
- Return the ans.
- The main idea of this approach is based on the following two concepts:
- If N >= P, then N! will definitely contain P!. So, N! % P = 0.
- Otherwise, we use Wilson’s and Fermat’s concepts.
- According to Wilson’s theorem: (P - 1)! -1 mod P for all prime P.
- Let us try to understand this approach by using an example, suppose we need to find (14! % 17). By Wilson’s theorem, 16! is -1. So, our problem only remains to find the [(-1) * modInverse(15,17) * modInverse(16,17)] % 17.
- Now, to find modInverse, we can use Fermat’s Little Theorem.
- This approach is mainly used when the difference between P and N is small.
Similar problems
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Co-Prime
Hard
Posted: 14 Dec, 2022
First Digit One
Moderate
Posted: 14 Oct, 2025
Special Digit Numbers
Hard
Posted: 31 Oct, 2025