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:
    def getPermutation(self, n: int, k: int) -> str:
        res, nums = "", list(range(1, n + 1))

        k -= 1

        for n in range(n, 0, -1):
            index, k = divmod(k, math.factorial(n-1))
            res += str(nums.pop(index))

        return res

Leave a Reply

Your email address will not be published.