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 kth 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();

}
}


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.


Click Follow button to receive updates from us instantly.

Please let us know about your views in comment section.

Happy Coding...😍

Comments

Popular posts from this blog

First Unique Character in a String

Balanced Binary Tree

Majority Element

Sequential Digits