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.
1def getPermutation(n: int, k: int) -> str:
2 import math
3 numbers = list(range(1, n+1))
4 k -= 1
5 result = []
6
7 for i in range(n, 0, -1):
8 idx = k // math.factorial(i-1)
9 result.append(numbers.pop(idx))
10 k %= math.factorial(i-1)
11 return ''.join(map(str, result))
12
13n = 3
14k = 3
15print(getPermutation(n, k))This Python implementation utilizes math.factorial to handle factorial calculations. It efficiently builds the permutation using list manipulation to determine which element should appear in each position.
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.