151 DSA Problem journey

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:

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "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