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


  • 1
    T

    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);
        }
    }

Log in to reply
 

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