282. Kth Ordering
A museum lays out n numbered exhibits (labelled 1 to n, each used once) along a corridor. Every possible left-to-right arrangement is written as a digit string, and all arrangements are listed in ascending dictionary order, so with three exhibits the list begins 123, 132, 213 and so on.
Given n and a 1-indexed rank k, return the arrangement that sits at position k in that list, as a string of n digits. Enumerating arrangements one by one is far too slow for n = 9; use the factorial number system to decide each digit directly in O(n^2) time and O(n) space.
Example 1
- Input:
- n = 5, k = 37
- Output:
- "24135"
- Explanation:
Position 37 of the 120 arrangements of five exhibits is 24135.
Example 2
- Input:
- n = 1, k = 1
- Output:
- "1"
- Explanation:
A single exhibit has only one arrangement.
Example 3
- Input:
- n = 6, k = 720
- Output:
- "654321"
- Explanation:
The last of the 720 arrangements is the digits in descending order.
Constraints
1 ≤ n ≤ 9
1 ≤ k ≤ n!
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)