Sponsored
Sponsored
This approach leverages the factorial number system, where the number of permutations starting with a particular digit can be determined by the factorial of (n-1). We adjust k for zero-based indexing and deduct permutations as we determine each digit sequentially.
Time Complexity: O(n^2) due to potential shifts in the numbers array.
Space Complexity: O(n) for storing factorials and numbers.
1function getPermutation(n, k) {
2 let numbers = Array.from({length: n}, (_, i) => i + 1);
3 let factorial = [1];
4 for (let i = 1; i < n; i++)
5 factorial[i] = factorial[i - 1] * i;
6 k--;
7 let result = '';
8 for (let i = n; i > 0; i--) {
9 let index = Math.floor(k / factorial[i - 1]);
10 result += numbers[index];
11 numbers.splice(index, 1);
12 k %= factorial[i - 1];
13 }
14 return result;
15}
16
17const n = 3, k = 3;
18console.log(getPermutation(n, k));This JavaScript implementation uses arrays to manage the ongoing list of numbers and computes factorial indices to choose digits. It consecutively constructs the final permutation string.
This approach generates permutations using a traditional backtracking method, with the goal of finding the k-th permutation without necessarily generating all permutations explicitly.
Time Complexity: O(n!) for generating permutations.
Space Complexity: O(n) due to recursion and string storage.
1import
This Python solution makes use of itertools.permutations to dynamically produce permutations, leveraging itertools.islice to directly arrive at the k-th permutation.