### LeetCode June Challenge - Day 20

**Problem:** LeetCode June Challenge - Day 20

**Ideas:**

- It’s easy to get the first digit of the permutation, since there are (n-1)! permutations starting with each one of them.
- 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;
}
};
```