K-th Permutation Sequence

Moderate

0/80

Average time to solve is 15m

Contributed by

62 upvotes

Asked in companies

Problem statement

You have been given two integers ‘N’ and ‘K’. Your task is to find the K-th permutation sequence of numbers from 1 to ‘N’. The K-th permutation is the K-th permutation in the set of all sorted permutations of string 1 to ‘N’.

For example :

If ‘N’ = 3 and ‘K’ = 4. Then all permutations for ‘N’ = 3 are “123”, “132”, “213”, “231”, “312”, “321”. So the 4-th permutation is “231”.

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

Input Format:

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’, respectively.

Output Format:

The only line of output contains a string of K-th permutation sequence of numbers from 1 to ‘N’.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’ <= 9
1 <= ‘K’ <= N!

Time Limit: 1 sec

Sample Input 1:

2
2 1
3 6

Sample Output 1:

12
321

Explanation For Sample output 1:

For the first test case, ‘N’ = 2. So all permutations are “12”, “21”. Now ‘K’ = 1, so the 1st permutation is “12”.

For the second test case, ‘N’ = 3. So all permutations are  “123”, “132”, “213”, “231”, “312”, “321”. Now ‘K’ = 6, so the 6th permutation is “321”.

Sample Input 2:

2
4 3
1 1

Sample Output 2:

1324
1

Hint 1

Hint 2

Try to find all permutations of sequence 1 to ‘N’.

Approaches (2)

Approach 1

Approach 2

Naive Approach

Naively we will generate all permutations of sequence 1 to ‘N’ and store them in an array. We will use recursion to generate all permutations.

Here is the algorithm:

We will call a void function permutate. The permutate function will work as follows (here ‘s’ and ‘ans’ denotes the string we passed to the function and the string we are generating, respectively):
- If s.length() == 0 (Base Case)
  - Push the string ‘ans’ into the array where all permutations will be stored.
- We run a for loop from i = 0 to s.length():
  - Do a recursive call by removing i-th character from ‘s’ and adding it to ‘ans’.
Finally, return the K-th element of the array.

Time Complexity

O(N!), where ‘N’ is the length of each string.

There are a total N! permutations and to generate them we need O(N!) time.

Space Complexity

O(N!), where ‘N’ is the length of each string.

Since we are storing all the N! Permutations in an array. Hence the space complexity is O(N!).

(100% EXP penalty)

K-th Permutation Sequence

Console