# [C++] [0 ms] Illustrated O(n) solution

• This is mainly a mathematics problem. For a permutation set of digits, say 1,2,3,4:

• 1 2 3 4
• 1 2 4 3
• 1 3 2 4
• 1 3 4 2
• 1 4 2 3
• 1 4 3 2
• 2 1 3 4
• 2 1 4 3
....
• 4 3 2 1

As you can see, number of permutations start with "1" is 6 = (n-1)!. Similarly, number of permutations start with "2" is also (n-1)!. So, to determine the first number of the kth value, we only need to calculate (k-1)/(n-1)! . Once you get this number, remember to remove it from available digits list.

Then, you move to the 2nd number. Everything stays the same, except your new k now becomes k%(n-1)!.

And, Code (I don't know how to format, pasting code seems always get messed up...):

``````
/* Factorials, i.e. n! */
int const factorials[] { /* 0! */ 1, /* 1! */ 1, /* 2! */ 2, /* 3! */ 6, /* 4! */ 24, /* 5! */ 120, /* 6! */ 720, /* 7! */ 5040, /* 8! */ 40320, /* 9! */ 362880 };

class Solution {
public:
string getPermutation(int n, int k) {
// Available charactors '1' ~ 'n'.
vector<char> availableChars;
for (int i = 0; i < n; i++)
{
availableChars.push_back('1' + i);
}

string result;
k--;

// Calculate the digit on each position.
for (int i = 0; i < n; i++)
{
// Get the index of the digit in available digits set.
int idx = k / factorials[n-i-1];

// Add the digit to result string.
result.push_back(availableChars[idx]);

// Remove the digit from available digits set.
availableChars.erase(availableChars.begin() + idx);

k %= factorials[n - i - 1];
}

return result;
}
};
```
```

• I think, that worst case complexity is O(n^2) for your code.
`// Calculate the digit on each position. for (int i = 0; i < n; i++)`