Solution Explanation: Finding the Kth Permutation

This problem asks to find the k-th lexicographical permutation of the numbers from 1 to n. The solution uses a clever approach based on the factorial number system.

Core Idea:

The key is understanding that the number of permutations of n items is n!. We can use this to determine the digits of the k-th permutation sequentially.

1. First Digit: There are (n-1)! permutations starting with each digit from 1 to n. We can find the first digit by dividing k by (n-1)!. The quotient indicates which digit to choose.

2. Subsequent Digits: Once the first digit is chosen, we adjust k by subtracting the number of permutations that start with the digits before the selected one. This effectively reduces the problem to finding the (k')-th permutation of the remaining (n-1) digits. We repeat this process until all digits are determined.

Algorithm:

1. Precompute Factorials: Calculate factorials from 0! to (n-1)! and store them in an array.

2. Iterate and Choose Digits:

   • Iterate through the digits (1 to n).
   • For each digit, check if k is greater than the number of permutations starting with digits less than the current one. If it is, subtract that number from k and continue. If it isn't, that's the correct digit.
   • Mark the chosen digit as used.
   • Divide k by the factorial of the remaining digits to prepare for selecting the next digit.

Time and Space Complexity:

• Time Complexity: O(n^2). The nested loops in the code dominate the runtime. While the outer loop runs n times, the inner loop's maximum iterations reduce with each step. The overall complexity isn't strictly O(n), but it's close to linear and significantly better than O(n!).

• Space Complexity: O(n). This is due to the space needed for storing the factorials (and the used numbers in the vis array).

Code Examples (Python):

import math
 
def getPermutation(n, k):
    """
    Finds the k-th permutation of numbers 1 to n.
 
    Args:
        n: The number of digits.
        k: The desired permutation index (1-based).
 
    Returns:
        The k-th permutation as a string.
    """
    
    factorials = [1] * (n + 1)
    for i in range(2, n + 1):
        factorials[i] = factorials[i - 1] * i
 
    result = ""
    numbers = list(range(1, n + 1))
    k -= 1  # Adjust k to be 0-based index
 
    for i in range(n, 0, -1):
        index = k // factorials[i - 1]
        result += str(numbers[index])
        numbers.pop(index)
        k %= factorials[i - 1]
 
    return result
 
# Example usage
n = 3
k = 3
print(getPermutation(n, k))  # Output: 213
 
n = 4
k = 9
print(getPermutation(n,k)) # Output: 2314

This Python code implements the algorithm efficiently. The other languages provided in the original response follow a very similar approach, differing only in syntax. Remember that the key is the efficient use of factorials to guide the digit selection process.