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.
1using System;
using System.Collections.Generic;
class Program {
static string GetPermutation(int n, int k) {
var numbers = new List<int>();
for (int i = 1; i <= n; i++) numbers.Add(i);
int count = 0;
string permutation = string.Empty;
RecursePermute(numbers, k, ref count, ref permutation);
return permutation;
}
static void RecursePermute(List<int> numbers, int k, ref int count, ref string permutation) {
if (numbers.Count == 0 && ++count == k) return;
for (int i = 0; i < numbers.Count; i++) {
int current = numbers[i];
numbers.RemoveAt(i);
permutation += current.ToString();
RecursePermute(numbers, k, ref count, ref permutation);
if (count == k) return;
permutation = permutation.Substring(0, permutation.Length - 1);
numbers.Insert(i, current);
}
}
static void Main() {
int n = 3, k = 3;
Console.WriteLine(GetPermutation(n, k));
}
}This C# implementation employs recursive backtracking to build permutations. It involves incrementing a count until achieving the target permutation sequence.