K-th Permutation Sequence Of First N Natural Numbers

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in company
Hyper Verge

Problem statement

You’re given two integers N and K, your task is to find the Kth permutation of the sequence of first N natural numbers.

For Example :

If N = 3 and K = 3.
The Possible Permutations for N = 3 are {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}. 
In this list, the 3rd Permutation sequence is 2 1 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer T denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains two space-separated integers N and K, as specified in the problem statement.
Output Format : 
For each test case, print an array denoting the Kth permutation of the sequence of first N natural numbers.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <=  N <= 5 * 10^3
1 <= K <= min(N!, 5 * 10^3)

Time limit: 1 sec
Sample Input 1 :
2
2 2
2 1
Sample Output 1 :
2 1
1 2
Explanation of Sample Input 1 :
Permutation sequences for N = 2 are {1 2,2 1}. The second term in this sequence list is {2 1}, which is the answer to the first test case, and the first term in this sequence list is {1 2}, which is the answer to the second test case.
Sample Input 2 :
2
3 6
3 3
Sample Output 2 :
3 2 1
2 1 3
Explanation of Sample Input 2 :
Permutation sequences for N = 3 are {1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1}. The sixth term in this sequence list is {3 2 1}, which is the answer to the first test case and the third term in this sequence list is {2 1 3}, which is the answer to the second test case.
Hint

Generate all possible permutations of the sequence.

Approaches (2)
Recursive Approach
  1. We’ll make a function named ‘kthPermutation’ with two integer parameters n and k.
    1. Inside this function, we’ll make a 2 Dimensional array named ‘answer’ and an array named ‘v’ and then call our helper function kPermutationHelper(0, v, n, answer).
    2. Kth permutation will be answer[k-1].
  2. Call the recursive function ‘kthPermutationHelper’ with parameters: integer i, an array v, integer N, and a 2 Dimensional array named ‘answer’.
  3. Base case: if ‘i’ equal to N, then simply push ‘v’(a permutation of N) into ‘answer’ and return.
  4. Now we make a boolean array named ‘visited’ of size N+1 to mark the occurrences. Initially, we’ll fill this array with 0.
  5. Then mark all the numbers visited, which are present in the array ‘v’.
  6. Then we check if a number already exists in array v or not, by running a loop(loop variable j) from 1 till N.
    1. We first check if the current number ‘j’ already exists in our array ‘v’ or not. If it doesn’t exist in v, then we’ll place this number ‘j’ at this position.
    2. We do this by pushing ‘j’ into 'v’ and calling kthPermutationHelper(i+1, v, n, answer). After this do the pop operation, i.e, backtrack.
Time Complexity

O(N*N!), where N is the number whose Kth permutation sequence is to be found.

 

In total there are N! Permutations possible, and in each call, we iterate on the number, and there are N such numbers, which will cost us O(N) time. Hence, to generate all the permutations we’ll take O(N*N!) time.

Space Complexity

O(N*N!), where N is the number whose Kth permutation sequence is to be found.

 

As we are using a 2 Dimensional array with N! Columns and each column will have N rows to store the N! Possible permutations. Thus, the space complexity will be O(N*N!).

Code Solution
(100% EXP penalty)
K-th Permutation Sequence Of First N Natural Numbers
Full screen
Console