Last Updated: 4 Mar, 2021
Permutation Coefficient
Moderate
Asked in company
You are given two numbers ‘N’ and ‘K’. Your task is to find P(N, K). P(N, K) is the permutation coefficient given as P(N, K) = N! / (N - K)! where X! Is the product of first X natural number. Since this value may be large only find it modulo 10^9 + 7.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first and only line of each test case contains two integers ‘N’ and ‘K’.
Output Format:
For each test case, print a single line containing a single integer denoting the answer for that test case modulo 10^9 + 7.
Print the output of each test case 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’ <= 50
1 <= ’N’ <= 10000
0 <= ’K’ <= ’N’
Time Limit: 1 sec
Approaches
Explanation: The key idea is to precompute all P(N, K) for given values of ‘N’ and ‘K’.The recurrence relation for P(N, K) is given by P(N, K) = P(N - 1, K) + ‘K’ * P(N - 1, K - 1).
Algorithm:
- Create a 2d matrix ‘P[N + 1][K + 1]’ with initial value 0.
- Intialize ‘P[i][0]’ = 1 for all i 0 to ‘N’. (i.e. P(x, 0) equals 1)
- Run a loop from 'i' from1 to ‘N’. Inside this loop run another loop from 0 to min(i, k).
- Compute ‘P[i][j]’ which is given by ‘P[i][j]’ = ('P[i - 1][j]' + ‘(j * P[i - 1][j - 1])’ ) % (10^9 + 7) according to the recurrence relation.
- Return 'P[N][K]' in the end.
Explanation: The key idea is to expand n! and (n-k)!
n! = n * (n - 1).....(n - k + 1) * (n - k) * (n - k - 1)...1
n! = n * (n - 1)...(n - k + 1) * (n - k)!
P(n, k) = n * (n - 1)..(n - k + 1)*(n - k)! / (n - k)!
P(n, k) = n * (n - 1) * (n - 2)..*(n - k + 1).
P(n, k) is also given as the product of k terms from n.
Algorithm:
- Create a variable ‘ANS’ = 1.
- Run a loop from ‘i’ from 0 to 'K'.
- In each iteration multiply ans with ‘N - i’ such that ‘ANS’ = (ANS * (N - i) ) % MOD.
- Return ‘ANS’.
Similar problems