60. Permutation Sequence

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

Here k-=1

That is because when k is divisible by the group size, we want to assign it to the former group. E.g. group a: 1 2 group b: 3 4 group c: 5 6. Given 4//2=2 5//2=2. In order to keep 4 in group b and 5 in group c, we can decrease the number by 1 before dividing it. That is, (4-1)//2=1, (5-1)//2=2. If k-=1 seems confusing, you can also do index=k//math.factorial(n)-1 if k%math.factorial(n)==0 else k//math.factorial(n) which might seem verbose but more clear and produce same result.

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        fact = [1]
        nums = []
        res = ""
        for i in range(1,n+1):
            fact.append(fact[-1] * i)
            nums.append(str(i))
        k-=1
        while n > 0:
            idx = k // fact[n-1]
            k = k % fact[n-1]
            res += nums[idx]
            n-=1
            nums.remove(nums[idx])
        return res