HARD

Permutation Sequence

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

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

Example

Input:

n = 3, k = 3

Output:

"213"

Explanation: The permutations are ["123", "132", "213", "231", "312", "321"]. The 3rd permutation is "213".

Constraints

1 ≤ n ≤ 9
1 ≤ k ≤ n!

Solution: Math (Factorial Number System)

Time Complexity: O(n^2)
Space Complexity: O(n)

C++

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> numbers;
        int fact = 1;
        for (int i = 1; i <= n; ++i) {
            numbers.push_back(i);
            fact *= i;
        }
        --k; // convert to 0-based index
        string res;
        for (int i = n; i >= 1; --i) {
            fact /= i;
            int idx = k / fact;
            res += to_string(numbers[idx]);
            numbers.erase(numbers.begin() + idx);
            k %= fact;
        }
        return res;
    }
};