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.
1import java.util.ArrayList;
2
3public class Main {
4 public static String getPermutation(int n, int k) {
5 int[] factorial = new int[n];
6 ArrayList<Integer> numbers = new ArrayList<>();
7 factorial[0] = 1;
8 for (int i = 1; i < n; i++)
9 factorial[i] = factorial[i - 1] * i;
10 for (int i = 1; i <= n; i++)
11 numbers.add(i);
12
13 StringBuilder result = new StringBuilder();
14 k--;
15 for (int i = n; i >= 1; i--) {
16 int index = k / factorial[i - 1];
17 result.append(numbers.get(index));
18 numbers.remove(index);
19 k %= factorial[i - 1];
20 }
21 return result.toString();
22 }
23
24 public static void main(String[] args) {
25 int n = 3, k = 3;
26 System.out.println(getPermutation(n, k));
27 }
28}This Java solution uses an ArrayList for dynamic number storage. It calculates the required permutation by using factorial math to decide the sequence of digits, updating the list as digits are fixed.
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.
1#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string getPermutation(int n, int k) {
string numbers;
for (int i = 1; i <= n; i++)
numbers += to_string(i);
string result;
do {
k--;
if (k == 0) {
result = numbers;
break;
}
} while (next_permutation(numbers.begin(), numbers.end()));
return result;
}
int main() {
int n = 3, k = 3;
cout << getPermutation(n, k) << endl;
return 0;
}This C++ solution uses the standard library's next_permutation to iterate through permutations until the k-th is found, optimizing the traditional backtracking method.