[LeetCode] 60. Permutation Sequence

Problem : https://leetcode.com/problems/permutation-sequence/

When N = 3, we have below sequences : 

[1]  1 2 3

[2]  1 3 2

[3]  2 1 3

[4]  2 3 1

[5]  3 1 2

[6]  3 2 1

Initially,

Nums =  [1, 2, 3]

Total sequences are 3! =  3 * 2 * 1

There are 3 main groups.  In each group it is the full permutation of the rest numbers.

The first number of 3rd sequence =  (3 - 1) // 6 // 3 = 1.  Nums[1] == 2.  So the first number is 2.

Take 2 from the number array,

Nums = [1, 3]

Total sequences are 2! = 2 * 1

Now we need to locate the  (3-1) % 2 + 1 = 1, the 1st sequence of [1,3]'s full permutation.

There are 2 main groups. In each group it is the full permutation of the rest numbers.

So the first number of 1st sequence =  (1-1) // 2 // 1  = 0.  Nums[0] =  1. So the second number is 3.

Take 3 from the number array,

Nums = [1]

Total sequences is 1! = 1

Now we need to locate the (1 - 1) % 1 + 1 = 1, the 1st sequnce of [1]'s full permutation.

So the first number of 1st sequence = (1 - 1) // 1 // 1 =  0. Nums[0] = 1. So the thrid number is 1.

Time Complexity = O ( N )

Space Complexity =  O ( 1 ) 

from operator import imul

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        
        nums = [str(i) for i in range(1, n+1)]
        
        # total = n!
        total = reduce(imul, range(1,n+1))
        result = ""
        
        k -= 1  # number index starts from 0
        
        while n > 0:
            group = total // n
            
            i = k // group
            
            result += nums[i]
            nums.pop(i)
            
            k = k % group 
            
            total = total // n
            n -= 1
            
        return result