dsa · hard

Permutation Sequence

The permutations of 1, 2, …, n written in lexicographic order form a list of n! strings. Return the k-th of those strings (k is 1-based). Each permutation is the digits concatenated, with no spaces or commas.

Arguments

• n — upper bound of the digits 1..n to permute
• k — 1-based index of the permutation to return

Example

n = 3 lists "123", "132", "213", "231", "312", "321". k = 3 → "213".

n = 4, k = 9 → "2314".

n = 3, k = 1 → "123".

Constraints

1 <= n <= 9 1 <= k <= n! Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
3
3

Expected:
213

Example 2

Input:
4
9

Expected:
2314

Example 3

Input:
3
1

Expected:
123

Open in the Dojo editor