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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void getPermutation(int n, int k, char *result) {
6 int *factorial = malloc((n + 1) * sizeof(int));
7 int *numbers = malloc(n * sizeof(int));
8 factorial[0] = 1;
9 for (int i = 1; i <= n; i++)
10 factorial[i] = i * factorial[i - 1];
11 for (int i = 0; i < n; i++)
12 numbers[i] = i + 1;
13
14 k--;
15 for (int i = 0; i < n; i++) {
16 int index = k / factorial[n - 1 - i];
17 result[i] = '0' + numbers[index];
18 for (int j = index; j < n - 1; j++)
19 numbers[j] = numbers[j + 1];
20 k %= factorial[n - 1 - i];
21 }
22 result[n] = '\0';
23
24 free(factorial);
25 free(numbers);
26}
27
28int main() {
29 int n = 3, k = 3;
30 char result[10];
31 getPermutation(n, k, result);
32 printf("%s\n", result);
33 return 0;
34}This C solution involves precomputing factorials and maintaining an array of available numbers. We reduce k by dividing and modulo operations to select which number should appear next in the permutation sequence.
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>
2#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.