Find the k-th permutation of the numbers from 1 to n in lexicographic order.
Permutation Sequence
Given two integers n and k, consider all permutations of the numbers 1 through n sorted in lexicographic order. Return the k-th permutation in that ordering.
You should construct the permutation directly rather than generating every permutation.
Example
For n = 3, the permutations in order are:
123132213231312321
So for k = 4, the answer is 231.
Input Format
Input
- Two integers
nandk.
Interpretation
- The set of values is
1, 2, ..., n. kis 1-indexed in lexicographic order.
Output Format
Output
- Return the
k-th permutation as a string of digits in lexicographic order.
Constraints
1 <= n <= 91 <= k <= n!- The answer is guaranteed to exist.
- Use each number from
1tonexactly once.
Example 1
Input
n = 3, k = 4
Output
231
Explanation
The lexicographic ordering is 123, 132, 213, 231, 312, 321. The 4th permutation is 231.
Example 2
Input
n = 4, k = 9
Output
2314
Explanation
There are 6 permutations for each fixed first digit. The 9th permutation falls in the block starting with 2, then the remaining choices lead to 2314.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.