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.
1using System;
2using 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.