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 <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6string getPermutation(int n, int k) {
7 vector<int> factorial(n, 1);
8 vector<int> numbers;
9 for (int i = 1; i < n; i++)
10 factorial[i] = factorial[i - 1] * i;
11 for (int i = 1; i <= n; i++)
12 numbers.push_back(i);
13
14 string result;
15 k--;
16 for (int i = n; i >= 1; i--) {
17 int index = k / factorial[i - 1];
18 result += to_string(numbers[index]);
19 numbers.erase(numbers.begin() + index);
20 k %= factorial[i - 1];
21 }
22 return result;
23}
24
25int main() {
26 int n = 3, k = 3;
27 cout << getPermutation(n, k) << endl;
28 return 0;
29}This C++ solution implements the problem using vectors to handle factorial calculations and number selection efficiently. We generate the permutation string by iteratively computing position indices.
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#
This C solution uses a recursive backtracking approach to generate permutations, counting them until reaching the desired k-th permutation, which is stored for output.