Factorial Again

Moderate
0/80
Average time to solve is 50m
profile
Contributed by
0 upvote
Asked in company
Flipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
3 11 
2 11

Sample Output 1 :

8
9

Explanation of the Sample Input 1:

In the first test case, the answer is 8 because (9! / 6 ^ 3) is equal to 362880 / 216, which is equal to 1680, and 1680 when divided by 11 leaves the remainder 8. Therefore 8 is the final answer.

In the second test case, the answer is 9 because (6! / 6 ^ 2) is equal to 720 / 36, which is equal to 20, and 20, when divided by 11, leaves the remainder 9. Therefore 9 is the final answer.
Hint

Can we use modular arithmetic?

Approaches (1)
Wilson Theorm

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.
Time Complexity

O((N - P)*log(N)), where ‘N’ is the number given and ‘P’ is the given prime number.

 

Since in the worst case, we are going till ‘N’ and doing binary exponentiation for each ‘N’ Hence the overall complexity will be O((N - P)*log(N)).

Space Complexity

O(1).
 

Since we are not using any extra space, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Factorial Again
Full screen
Console