LeetCode June Challenge - Day 20

Problem: LeetCode June Challenge - Day 20

Ideas:

  1. It’s easy to get the first digit of the permutation, since there are (n-1)! permutations starting with each one of them.
  2. The next digits are calculated doing the same thing, but with permutations of (n-i) elements. You also do not have elemeents {1,…,n-i}, but {1,…,n}-{the ones already picked}.

Solution:

class Solution {
public:
    string getPermutation(int n, int k) {
        int fact[n+1];
        fact[0] = 1;
        for(int i=1; i<=n; ++i)
            fact[i] = fact[i-1]*i;
        vector<int> v(n);
        for(int i=0; i<n; ++i) v[i] = i+1;
        k--;

        string ans;
        for(int i=n-1; i>=0; --i){
            int next = k/fact[i];
            ans += v[next]+'0';
            k = k%fact[i];
            v.erase(v.begin() + next);
        }
        return ans;
    }
};