Last Updated: 17 Jun, 2021
Factorial Again
Moderate
Asked in company
Ninja Kate has finally calmed down and decides to forgive Little Ninja Deepu, but she will not forgive him just like that. Finally, she agrees to forgive him because he can solve a mathematical question for her.
She gives Ninja Deepu a large number ‘N’ and a prime number ‘P’ and asks him to calculate ((3 * ‘N’ ) ! / ( 3! ^ ‘N’ ) )% ‘P.’
Your task is to help Little Ninja Deepu get back together with Ninja Kate.
For example:
Given ‘N’ = 2, ‘P’ = 11.
Then the answer will be 9. Because (6!) / (6 ^ 2) = 20, and 20 remainder 11 is 9. Therefore the answer is 9.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
Next, ‘T’ lines contain two space-separated integers ‘N,’ where ‘N’ is the number given and ‘P,’ denoting the prime-number given to us.
Output Format :
For each test case, You are supposed to return the answer.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10 ^ 4
1 <= ‘P’ <= 10 ^ 5
Time Limit: 1sec.
Approaches
Furthermore, calculate numerator and denominator separately and then divide them and return the final answer, this can be done using Fermat's Theorem i.e.
For calculating ((3 * ‘N’ ) ! / ( 3! ^ ‘N’ ) )% ‘P.’, we will first calculate (3*N)! %P And then calculate ((3!)^N)%P.
For calculating the numerator, the Wilson theorem is a good choice.
Wilson’s theorem states that a natural number p > 1 is a prime number if and only if
(‘P’ - 1) ! ≡ -1 mod ‘P’
OR (‘P’ - 1) ! ≡ (‘P’ - 1) mod ‘P’
Note that ‘N’! % ‘N’ is 0 if ‘N’ >= ‘P’. This method is mainly useful when ‘P’ is close to the input number ‘N’.
Now, for calculating the denominator or (1/((3!)^N))%P, we can use the Fermat's theorem.
Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ‘a’ ‘p’ – ‘a’ is an integer multiple of ‘p’, where ‘p’ is a prime number
a^p ≡ a (mod p) or a^(p-1) = 1 (mod p) or a^(p-2) = a^(-1) (mod p)
It means for calculating (1/((3!)^N))%P or (1/((6)^N))%P, we can calculate 6^(P - 2) %P.
Then, we will multiply both the terms to get the final answer.
The steps are as follows:
- Multiply ‘N’ by 3 since we have to find the ‘3*N’ factorial.
- Maintain a variable ‘num’ which is the numerator.
- Loop from 1 to ‘N’, and at every iteration, we use a helper function, ‘modInverse’, which takes ‘i’, and ‘P’ as input parameters and multiplies them according to modular arithmetic described above using Wilson Theorem.
- Maintain a variable ‘den’, which is the denominator.
- ‘Den’ can be calculated using the helper function ‘power’, which takes the number ‘6’ because 3! It is essentially 6, ‘N / 3’ and ‘P’ as input and performs binary exponentiation.
- Finally, Maintain a variable ‘ans’, which denotes the final answer.
- We divide ‘num’ and ‘den’ using the helper function ‘modDivide’, which takes ‘num’, ‘den’, and ‘P’ as input parameters, and uses Fermat's Theorem.
- Finally, we return ‘ans’ as the final answer.