Fermat Little Theorem

Moderate
0/80
Average time to solve is 50m
1 upvote
Asked in company
Codenation

Problem statement

You are given two integers 'n' and 'r' and a prime number 'p'. Your task is to find (nCr) % p where nCr can be calculated as n! / (r! * (n - r)!).

Note :

N!  =  1 * 2 * 3 *... N
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test case contains three space-separated integers 'n', 'r', and 'p'.
Output format : 
For each test case, print a single line containing an integer representing the value of (nCr) % p.

The output of each test case will be printed on a separate line.
Note: 
You don't need to input or print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5 
1 <= n, r, p <= 5 * 10 ^ 2
p is prime number.

Time limit: 1 sec.
Sample Input 1 :
2 
5 2 11
4 3 13
Sample Output 1 :
10
4
Explanation for Sample Output 1:
In test case 1, 
n = 5, r = 2, and p = 11
n C r = 5 C 2 = (5 * 4) / (2!) = 10
n C r % p = 10 % 11 = 10. 
So the answer will be 10.

In test case 2,
n = 4, r = 3, and p = 13 
n C r = 4 C 3 = 4 C 1 = 4 
n C r % p = 4 % 13 = 4. 
So the answer will be 4.
Sample Input 2 :
2
5 2 17
10 2 13
Sample Output 2 :
10
6
Hint

Try to find the inverse modulo and then apply dynamic programming to calculate the binomial expression. Try to find inverse using Fermat little theorem.

Approaches (1)
Fermat Little Theorem

Expression nCr = fact(n) / (fact(r) * fact(n - r)) 

Here fact() means factorial.

 nCr % p = (fac[n] * powInverse(fac[r], 1) % p * powInverse(fac[n - r], 1) % p) % p; (From Fermat Little Algorithm) which will further be broken down to

nCr % p = (fac[n] % p * pow(fac[r], p - 2) % p * pow(fac[n - r]), p - 2) % p

 

Here powInverse() means inverse modulo under p i.e (1 / n) % p and pow() means power under modulo p.

To calculate the factorial we can maintain a dp array such that dp[X] = dp[X - 1] * X as X! = (X) * (X - 1)!. Where ‘X’ is some integer. And the factorial of the required number can be found at the last index of dp array.

 

Algorithm :

 

  • Make a function, say ‘powInverse’ which will calculate us (X ^ (-1)) modulo ‘p’ taking arguments ‘n’ and ‘p’.
  • Make a function, say ‘pow’ which will calculate the power of a number modulo ‘p’ taking arguments ‘x’ for which the power is to be calculated, ‘y’ denoting power, and ‘p’.
  • If (n < r) return 0, as nCr for n < r is 0.
  • If r = 0, then return 1.
  • Make a dp array say ‘dp[]’ of length ‘n + 1’ to store the factorial of the number modulo p.
  • Make dp[0] = 1 as Factorial of 0 is 1.
  • Iterate from ‘i’ = 1 till ‘i’ = N
    • Store dp[i] = (dp[i - 1] * i) % p.
  • Return (dp[n] * powInverse(dp[r], p) % p * powInverse(dp[n - r], p) % p) % p to the given function.

 

Description of ‘pow’ function:

Function to calculate (x ^ y) % p.

  • First, initialize a variable ‘ans’ which will store the power of the number modulo ‘p’ and initialize it to 1.
  • Update ‘x’ as x = x % p if ‘x’ is more than or equal to ‘p’.
  • Make an iteration for ‘y’ until it is a positive integer.
    • Check if ‘y’ is odd, if odd then:
      • Multiply ‘x’ with the ‘ans’ and modulo the result obtained and store it in ‘ans’.
      • Do modular squaring of 'x' i.e. do 'x' = ('x' * 'x') % 'p'.
  • Return ‘ans’ to the function ‘pow’.

 

Description of ‘powInverse’ function:

The function will find inverse modulo of 'n' under ‘p’, i.e. (1 / n ) % p.

  • Return the function ‘pow (n, p - 2, p)’
Time Complexity

O(N + log(P)), where ‘N’ is the given integer ‘n’ and ‘P’ is the given integer ‘p’.

 

As calculating the factorial takes O(N) int the given function and the function ‘pow' takes O(log (P - 2)) to calculate the power. So, the overall time complexity will be O(N + log (P)).

Space Complexity

O(N),  where ‘N’ is the given integer ‘n’ .


As we are using an auxiliary space of size N to calculate the factorial of the number. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Fermat Little Theorem
Full screen
Console