Permutation Coefficient

Moderate

0/80

Average time to solve is 15m

Contributed by

10 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5 3 
4 4

Sample Output 1:

60
24

Explanation For Sample Input 1:

For first case:
Ans = 5! / (5 - 3)! = 5! / 2!
5! is 120 and 2! is 2
Ans = 120/2 = 60

For second case :
Ans = 4! / (4 - 4)! = 4! / 0!
0! is 1 and 4! is 24
Ans = 24

Sample Input 2

2
6 0 
4 1

Sample Output 2:

1
4

Explanation For Sample Input 2:

For first case:
Ans = 6! / (6 - 0)! = 6! / 6!
6! is 720
Ans = 720/720 = 1

For second case :
Ans = 4! / (4 - 1)! = 4! / 3!
3! is 6 and 4! is 24
Ans = 24/6 = 4

Hint 1

Hint 2

Try to calculate all P(n, k) by formula of P(n, k).

Approaches (2)

Approach 1

Approach 2

Pre Computation Approach

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.

Time Complexity

O(N*K), where ‘N' and ‘K’ are the number given numbers.

We are precomputing total N*K values . Precomputing each value takes O(1) time. Hence time complexity is O(N*K). When N equals K Time Complexity will be O(N^2)

Space Complexity

O(N*K), where ‘N' and ‘K’ are the number given numbers.

To store N*K values we create an auxiliary matrix of size N*K. When N equals K Space Complexity will be O(N^2)

(100% EXP penalty)

Permutation Coefficient

Console