# Share my Python solution with detailed explanation

• The idea is as follow:

For permutations of n, the first (n-1)! permutations start with 1, next (n-1)! ones start with 2, ... and so on. And in each group of (n-1)! permutations, the first (n-2)! permutations start with the smallest remaining number, ...

take n = 3 as an example, the first 2 (that is, (3-1)! ) permutations start with 1, next 2 start with 2 and last 2 start with 3. For the first 2 permutations (123 and 132), the 1st one (1!) starts with 2, which is the smallest remaining number (2 and 3). So we can use a loop to check the region that the sequence number falls in and get the starting digit. Then we adjust the sequence number and continue.

``````import math
class Solution:
# @param {integer} n
# @param {integer} k
# @return {string}
def getPermutation(self, n, k):
numbers = range(1, n+1)
permutation = ''
k -= 1
while n > 0:
n -= 1
# get the index of current digit
index, k = divmod(k, math.factorial(n))
permutation += str(numbers[index])
# remove handled number
numbers.remove(numbers[index])

return permutation``````

• You can move factorial outside of the loop and call it only once, given that n is decreasing by 1 every iteration.

• similar idea! may be a little faster, without extern lib.

``````def getPermutation(self, n, k):
elements = range(1, n+1)
NN = reduce(operator.mul, elements) # n!
k, result = (k-1) % NN, ''
while len(elements) > 0:
NN = NN / len(elements)
i, k = k / NN, k % NN
result += str(elements.pop(i))
return result``````

• This post is deleted!

• what is the runtime of you algorithm?
is remove takes On time?

• @tju_xu97 divmod is builtin function

• @Zura thank you!

• Easy to understand

``````class Solution(object):
def getPermutation(self, n, k):
nums = map(str,range(1,10))
k -= 1
factorial = [1] * n
for i in range(1, n):
factorial[i] = factorial[i - 1] * i
res=[]
for i in range(n):
index = k / factorial[n - 1 - i]
res.append(nums[index])
nums.remove(nums[index])
k = k % factorial[n - 1 - i]
return ''.join(res)
``````

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