Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

 class Solution {
    public String getPermutation(int n, int k) {

    int[] factorial = new int[n];
    int i;
    StringBuilder sb = new StringBuilder();
    ArrayList<Integer> num = new ArrayList<Integer>();

    for (i = 0; i < n; i++) {
        num.add(i + 1);
        factorial[i] = i == 0 ? 1 : i * factorial[i - 1];
    }

    while (n > 0) {
        int remaining = ((k - 1) % factorial[n - 1]) + 1;
        sb.append(num.remove(((k - 1) / factorial[n - 1])));
        n--;
        k = remaining;
    }

    return sb.toString();

}
}

Try it on Leetcode

Here, we are going to solve with help of factorial array and an arraylist  of n numbers. This solution can be come up only after many different way of attempting to get solution. After many ways, finally I come up with one of solution

Below are steps to solve the problem.,

1) Create an arraylist to store 1 to n numbers while creating those list, create another array to store factorial of each number so that no need to do factorial again and again.

2) The value of (k-1) / (n-1)! represents element in the arraylist and that value should be removed and appended to the answer string.

3) Now set value of  k = (k-1) % (n-1)!, and n= n -1 to decide the next digit. Similarly nth = (k-1) / (n-1)!  Repeat that procedure until n ==0.

4) Finally output string contains kth permutation sequence.

[Example]

Let's be more clear and take n = 3, k = 3 as example.

a) First build you num array list as  = {1,2,3}; Also factorial array as {1, 2, 6}.

b) Then nth = (k-1) / (n-1)! = 2/2 = 1. which mean arrayList[1] should be removed and place to your answer string. Now answer is "2".

c) Now set k = (k-1) % (n-1)! +1 = 2%2 +1 = 1, and n= n -1 = 2 to decide the next digit. Now similar to step (b) in example = (k-1) / (n-1)! = 1/2 = 0; note that now arrayList[0] = 1 since 2 . Now answer is "21". Again do steps (b), (c) and you will get 3. Finally answer string contains "213".  Repeat that procedure until n ==0.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

Click Follow button to receive updates from us instantly.

Please let us know about your views in comment section.

Happy Coding...😍