Q19: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:
"123""132""213""231""312""321"
Given n and k, return the k<sup>th</sup> permutation sequence.
Example :
Input: n = 3, k = 3
Output: "213"
Solution:
class Solution {
public:
string getPermutation(int n, int k) {
string result = "";
vector<int> nums;
// Fill nums vector with numbers from 1 to n
for (int i = 1; i <= n; ++i) {
nums.push_back(i);
}
// Factorial lookup for quick computation
vector<int> factorial(n + 1, 1);
for (int i = 1; i <= n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
// Adjust k to 0-based index
--k;
// Generate the kth permutation
for (int i = n; i > 0; --i) {
int index = k / factorial[i - 1];
result += to_string(nums[index]);
nums.erase(nums.begin() + index);
k %= factorial[i - 1];
}
return result;
}
};
Explantion:
>The function getPermutation takes two parameters, n (the size of the set) and
k (the kth permutation to find). We initialize an empty string result to store
the final permutation and a vector nums to represent the numbers from 1 to n.
>We create a vector factorial to store the factorial values. This is used to quickly
calculate the index of the current digit in the permutation.
>We subtract 1 from k to make it 0-based, as array indices in C++ start from 0.
>We iterate from n to 1. For each iteration, we calculate the index of the
current digit in the permutation based on the value of k and the factorial values.
We then append the corresponding digit to the result string, remove it from the nums
vector, and update k for the next iteration
>Declare the result.
#Happy new year to everyone