Ninja And The New Year Guests

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
Red HatCapegemini Consulting India Private LimitedNagarro Software

Problem statement

Ninja has organized the new year party and invited all the programmers for it, as being the programmer also has been invited by Ninja.

To detect whether the guest is a programmer or not, Ninja has set some tasks for them, such that only programmers can code them.

You have also been asked to solve and code the following task to verify your identity.

Given two integers, 'N' and 'K' find the number of permutation arrays of 'N' integers from 0 to 'N' - 1 satisfying the below condition.

There should be at least 'K' positions in the array such that 'ARR[I] = I' ( 0 <= I < N ) satisfies.

You are required to output the answer modulo 10^9 +7.

EXAMPLE: 
Input: 'N' = 4 'K' = 3 
Output: 1

There is only one permutation [0, 1, 2, 3] such that a number of elements with 'ARR[I] = I' is 'K' = 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, there will be only one line containing two integers' N' and 'K'.
Output format : 
For each test case, print the number of permutations modulo 10^9 + 7 satisfying the number of elements with 'ARR[I] = I' is 'K'.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10^4
4 <= 'N' <= 10^18
'N - 4' <= 'K' <= 'N'
1 <= K

Time Limit: 1sec
Sample Input 1 :
2
4 3
4 2
Sample Output 1 :
1
7
Explanation Of Sample Input 1 :
For the first test case, there is only one permutation [0, 1, 2, 3] such that a number of elements with 'ARR[I] = I' is 'K' = 3.

There are below 7 permutations satisfying the condition for the second test case.

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 3, 2, 1]
[0, 2, 1, 3]
[3, 1, 2, 0]
[2, 1, 0, 3]
[1, 0, 2, 3]
Sample Input 2 :
2
4 4
5 4
Sample Output 2 :
1
1
Hint

Can you check for all possible permutations?

Approaches (2)
Brute Force Approach

Approach: We will recursively find all possible permutations and then check for each of them whether it is following the condition or not.

 

We will maintain a counter based on that and increment it when the current permutation satisfies the condition.

 

Algorithm :  

 

// It is a recursive function to get all the permutations of the current array 'arr'.

void getPermutations(arr, index, k, ans)

  1. If 'index' >= 'arr.size()' :
    • Initialize the variable 'count' by 0.
    • Run a loop over array 'arr'
      • If 'arr[i] == i' then increment 'count' by 1.
    • If 'count' >= 'k' then increment 'ans'.
    • Call return.
  2. Run a loop from 'index' to 'arr.size()'.
    • Swap 'arr[index]' and 'arr[i]'.
    • Call 'getPermutations(arr, index + 1, k, ans)'.
    • Swap 'arr[index]' and 'arr[i]' again.
       

int numberOfPermutations(n, k)

  1. Initialize the variable 'mod' by 1e9 + 7 and 'ans' by 0.
  2. Initialize an empty vector 'arr'.
  3. Run a loop from 0 to 'n - 1' and push each index in 'arr'.
  4. Call 'getPermutations(arr, 0, k, ans)'
  5. Return 'ans % mod'
Time Complexity

O(N * N!), where 'N' is the input integer

 

We are recursively finding all permutations, there will be N! recursive calls, and for each call, there will be a running loop with N iterations. Hence the overall time complexity will be O(N * N!).

Space Complexity

O(N), where 'N' is the input integer
 

We are using the recursion, and the recursive call stack can have maximum 'N' elements for this problem. Hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And The New Year Guests
Full screen
Console