Ninja and the New Year Guests Problem
Ninja has organized a new year party and wants to verify if the guests are programmers by challenging them with a coding task. As an invited programmer, you're tasked to solve it.
You need to compute the number of permutations of integers from 0 to N-1 such that at least K positions in the permutation satisfy ARR[I] = I
(where 0 ≤ I < N).
The result should be given modulo 109 + 7.
Input:
The first line contains an integer 'T', indicating the number of test cases.
Each test case consists of a single line with two integers 'N' and 'K'.
Output:
For each test case, print the number of valid permutations modulo 10^9 + 7.
Example:
Input:
'N' = 4 'K' = 3
Output:
1
Explanation: There is only one permutation [0, 1, 2, 3] such that the number of elements satisfying ARR[I] = I
is K = 3.
Constraints:
1 ≤ 'T' ≤ 10^4
4 ≤ 'N' ≤ 10^18
'N - 4' ≤ 'K' ≤ 'N'
1 ≤ K
- Time Limit: 1 second
Note:
You do not need to print anything. Just implement the provided function.
AnswerBot
2d
Compute the number of valid permutations of integers from 0 to N-1 such that at least K positions satisfy ARR[I] = I.
Use dynamic programming to solve the problem efficiently.
Consider the cases where K...read more
Help your peers!
Add answer anonymously...
Top Nagarro Software Developer interview questions & answers
Popular interview questions of Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app