# Concise C# O(n) solution - Run time is actually constant if n = [1,10] as per question.

• Explanation : Since n! = n*(n-1)!, among the n! permutations of {1,2,3,4...n}, (n-1)! elements start with 1, (n-1)! elements start with 2... etc. The kth (assuming k is 0 based index) sequence of this set starts with k/Fatorial(n-1)th number in the array [1,2,3,...n]. Now the problem has reduced to finding the k%Fatorial(n-1) th sequence among the remaining n-1 elements.

``````public class Solution
{
List<int> Nums = new List<int>{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] Factorial = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
public string GetPermutation(int n, int k)
{
return GetPermutationHelper(n, k - 1, string.Empty);
}

public string GetPermutationHelper(int n, int k, string permute)
{
if (n == 0)
{
return permute;
}
int groupNum = k / Factorial[n - 1];
permute = permute + Nums[groupNum];
int seqNum = k % Factorial[n - 1];
Nums.RemoveAt(groupNum);
return GetPermutationHelper(n-1, seqNum, permute);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.