[Leetcode 06/2020] Permutation Sequence

Problem:
//============================================
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"

//============================================
This problem is really easy using C++ with STL library. Using next_permutation(string.begin(), string.end()) function, we can use a while loop as the solution below.

class Solution {
public:
    string getPermutation(int n, int k) {
        string s ="";
        for(int i =1;i <=n; i++)
        {
            s+= to_string(i);
        }
        cout<<s<<endl;
        while(k>1) //First time count from 1
        {
            k--;
            next_permutation(s.begin(), s.end());

        }
        return s;
    }
};

Other efficient method: (https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/)
Explanation with simple example {1,2,3,4} and k =8
Step 1: First we find the first index using the formula
index = k / (n-1)! (with k = k-1)
so first index = 7/(4-1)! = 1 => first index = 1, we have {2,.,.}
Step 2: Then we find the second index with k now will be calculated to k1 = k%(n-1)! = 7%6 = 1 so next index = 1/(3-1)!=1/2! = 0 in the set {1,3,4} so 1 will be the next number. We have {2,1,.,.}
Step 3: Similarly, we calculate k2 = 1%(2!) = 1. next index = k2/(n-3)! = 1/1! = 1 in the set {3,4}. So 4 will be the next number. We have {2,1,4,.}
Finally we have last number remaining. So we just fill in and the final result is {2,1,4,3}

class Solution {
public:
    int factorial(int n) 
    { 
        return (n==1 || n==0) ? 1: n * factorial(n - 1);  
    } 
    int findFirstNumIndex(int& k, int n) 
    { 

        if (n == 1) //last number remaining in set, so return the index 0
            return 0; 
        n--; 

        int first_num_index; 
        int n_partial_fact = factorial(n);

        // First position of the kth sequence will be at index = k / (n-1)!  
        first_num_index = k / n_partial_fact; 

        k = k % n_partial_fact; 

        return first_num_index; 
    } 
    string getPermutation(int n, int k) {
        string ans = ""; 

    set<int> s; 

    // Insert all natural number in set {1,2,3,4}
    for (int i = 1; i <= n; i++) 
        s.insert(i); 

    set<int>::iterator itr; 

    // Mark the first position 
    itr = s.begin(); 

    // K starts couting from 1 
    k = k - 1; 

    for (int i = 0; i < n; i++) { 

        int index 
            = findFirstNumIndex(k, n - i); 

        advance(itr, index); //get the value of number in the index. 

        ans += (to_string(*itr)); 

        // remove current number from the set 
        s.erase(itr); 

        itr = s.begin(); 
    } 
    return ans; 

Please leave comment if I made any mistakes. Thanks a lot.