Given two integers N and K. Find the kth permutation sequence of first N natural numbers.
 
Example 1:
Input: 4 3
Output: 1324
Explanation: 
Permutations of first 4 natural numbers:
1234,1243,1324,1342,1423,1432.....
So the 3rd permutation is 1324. 
Example 2:
Input: 3 5
Output: 312
Explanation: 
Permutations of first 3 natural numbers:
123,132,213,231,312,321.
So the 5th permutation is 312. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kthPermutation() which takes two integers N and K as input parameters and returns an string denoting the kth permutation. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 9
1 <= K <= N!

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)

Starter code:
from typing import List





class Solution:

    def kthPermutation(self, n : int, k : int) -> str:

        # code here

        



Solutions:
from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		inp = []
		fact = 1
		for i in range(1, n + 1):
			inp.append(i)
			fact *= i
		fact = fact // n
		i = n - 1
		k = k - 1
		ans = ''
		while i >= 1:
			block = k // fact
			ans += str(inp[block])
			inp.pop(block)
			k = k % fact
			fact = fact // i
			i -= 1
		ans += str(inp.pop())
		return ans


from typing import List

class Solution:

	def factorial(self, num):
		ans = 1
		for i in range(1, num + 1):
			ans *= i
		return ans

	def kthPermutation(self, n: int, k: int) -> str:
		size = self.factorial(n - 1)
		k -= 1
		arr = [i for i in range(1, n + 1)]
		ans = ''
		while True:
			idx = int(k // size)
			ans += str(arr.pop(idx))
			if len(arr) == 0:
				break
			k %= size
			size /= len(arr)
		return ans


from typing import List
from itertools import permutations

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		l = list(range(1, n + 1))
		iter = permutations(l)
		for i in iter:
			k -= 1
			if k == 0:
				out = ''
				for j in i:
					out += str(j)
				return out
		return ''


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		factorial = 1
		numbers = []
		for i in range(1, n):
			factorial = factorial * i
			numbers.append(i)
		numbers.append(n)
		k = k - 1
		ans = ''
		while True:
			ans += str(numbers[k // factorial])
			numbers.pop(k // factorial)
			if len(numbers) == 0:
				break
			k = k % factorial
			factorial = factorial // len(numbers)
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		f = 1
		l = []
		for i in range(1, n):
			f *= i
			l.append(i)
		k -= 1
		l.append(n)
		x = ''
		while True:
			x += str(l[int(k / f)])
			l.remove(l[int(k / f)])
			if len(l) == 0:
				break
			k %= f
			f /= len(l)
		return x


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		nums = []
		for i in range(1, n):
			fact = fact * i
			nums.append(i)
		nums.append(n)
		k = k - 1
		ans = ''
		while True:
			ans += str(nums[k // fact])
			nums.remove(nums[k // fact])
			if len(nums) == 0:
				break
			k = k % fact
			fact = fact // len(nums)
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		nums = [i + 1 for i in range(n)]
		fact = [0] * 10
		fact[0] = 1
		fact[1] = 1
		for i in range(2, 10):
			fact[i] = i * fact[i - 1]
		ans = []

		def perms(nums, k):
			if len(nums) == 0:
				return
			n = len(nums)
			idx = k // fact[n - 1]
			if k % fact[n - 1] == 0:
				idx -= 1
			k = k - idx * fact[n - 1]
			ans.append(nums[idx])
			nums = nums[:idx] + nums[idx + 1:]
			perms(nums, k)
		perms(nums, k)
		res = 0
		for i in ans:
			res = res * 10 + i
		return res


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		nums = [i for i in range(1, n + 1)]
		factorials = [1]
		for i in range(1, n + 1):
			factorials.append(factorials[i - 1] * i)
		k -= 1
		result = ''
		for i in range(n, 0, -1):
			index = k // factorials[i - 1]
			k %= factorials[i - 1]
			result += str(nums[index])
			nums.pop(index)
		return result


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		str1 = []
		result = ''
		for i in range(1, n + 1):
			str1.append(str(i))
		temp = n
		fact = 1
		while temp:
			fact *= temp
			temp -= 1
		k = k - 1
		while n:
			fact //= n
			temp = k // fact
			k = k % fact
			result += str1[temp]
			str1.pop(temp)
			n -= 1
		return result


def findFirstNumIndex(k, n):
	if n == 1:
		return (0, k)
	n -= 1
	first_num_index = 0
	n_partial_fact = n
	while k >= n_partial_fact and n > 1:
		n_partial_fact = n_partial_fact * (n - 1)
		n -= 1
	first_num_index = k // n_partial_fact
	k = k % n_partial_fact
	return (first_num_index, k)

def findKthPermutation(n, k):
	ans = ''
	s = set()
	itr = []
	for i in range(1, n + 1):
		itr.append(i)
	k = k - 1
	for i in range(n):
		(index, k) = findFirstNumIndex(k, n - i)
		ans += str(itr[index])
		itr.pop(index)
	return ans

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		return findKthPermutation(n, k)


from typing import List

class Solution:

	def fact(self, a):
		if a <= 1:
			return 1
		return a * self.fact(a - 1)

	def kthPermutation(self, n: int, k: int) -> str:
		l = [x for x in range(1, n + 1)]
		k = k % self.fact(n)
		if n == 1:
			return '1'
		ans = []
		while l:
			nper = self.fact(n - 1)
			ind = (k - 1) // nper
			ans.append(str(l[ind]))
			del l[ind]
			k = k % nper
			n -= 1
		return ''.join(ans)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		arr = [i for i in range(1, n + 1)]
		dp = [1] * (n + 1)

		def fact(n):
			if n == 0 or n == 1:
				return 1
			dp[n] = n * fact(n - 1)
			return dp[n]
		dp[n] = fact(n)
		no = dp[n]
		ans = 0
		k -= 1
		i = 1
		while i <= n:
			ind = k // dp[n - i]
			ans = ans * 10 + arr[ind]
			arr.remove(arr[ind])
			k = k % dp[n - i]
			i += 1
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		permutation = []
		unused = list(range(1, n + 1))
		fact = [1] * (n + 1)
		for i in range(1, n + 1):
			fact[i] = i * fact[i - 1]
		k -= 1
		while n > 0:
			partlength = fact[n] // n
			i = k // partlength
			permutation.append(unused[i])
			unused.pop(i)
			n -= 1
			k %= partlength
		return ''.join(map(str, permutation))


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		num = []
		for i in range(1, n):
			num.append(i)
			fact *= i
		num += [n]
		ans = ''
		k -= 1
		while 1:
			ans += str(num[k // fact])
			num.pop(k // fact)
			if len(num) == 0:
				break
				c = 1
			k = k % fact
			fact = fact // len(num)
		return ans


class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		numbers = []
		for i in range(1, n):
			fact = fact * i
			numbers.append(i)
		numbers.append(n)
		k = k - 1
		ans = ''
		while True:
			ans += str(numbers[k // fact])
			numbers.pop(k // fact)
			if len(numbers) == 0:
				break
			k = k % fact
			fact = fact // len(numbers)
		return ans


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		ans = ''
		m = n - 1
		a = [str(i) for i in range(1, n + 1)]
		k -= 1
		for i in range(n):
			temp = k // math.factorial(m)
			k = k % math.factorial(m)
			m -= 1
			ans += a[temp]
			a.pop(temp)
		return ans


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		arr = []
		fact = 1
		for i in range(1, n):
			fact = fact * i
			arr.append(i)
		arr.append(n)
		k = k - 1
		ans = ''
		while True:
			ans += str(arr[k // fact])
			arr.pop(k // fact)
			if len(arr) == 0:
				break
			k = k % fact
			fact = fact // len(arr)
		return ans


from typing import List
from itertools import permutations

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		count = 0
		arr = [str(i) for i in range(1, n + 1)]
		for i in permutations(arr):
			count += 1
			if count == k:
				return int(''.join(i))


import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		i = 0
		swap = 1
		k -= 1
		arr = [i for i in range(1, n + 1)]
		while i < n:
			if math.factorial(n - i - 1) > k:
				i += 1
				swap = i + 1
			else:
				(arr[i], arr[swap]) = (arr[swap], arr[i])
				k -= math.factorial(n - i - 1)
				swap += 1
		arr = [str(i) for i in arr]
		return ''.join(arr)


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		nums = [str(i + 1) for i in range(n)]
		factorial = math.factorial(n)
		index = k - 1
		out = []
		while nums:
			factorial = factorial // len(nums)
			pos = index // factorial
			ans = nums.pop(pos)
			out.append(ans)
			index = index % factorial
		return ''.join(out)


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		l = [str(i + 1) for i in range(n)]
		fac = math.factorial(n)
		ans = []
		k = k - 1
		while l:
			fac = fac // len(l)
			ans.append(l.pop(k // fac))
			k = k % fac
		return ''.join(ans)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		numbers = []
		for i in range(1, n):
			fact *= i
			numbers.append(i)
		numbers.append(n)
		ans = ''
		k = k - 1
		while 1:
			temp = k // fact
			ans += str(numbers[temp])
			del numbers[temp]
			leng = len(numbers)
			if leng == 0:
				return ans
			k = k % fact
			fact //= leng


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		nums = []
		k -= 1
		result = ''
		fact = 1
		for i in range(1, n):
			nums.append(i)
			fact *= i
		nums.append(n)
		while True:
			result += str(nums[k // fact])
			nums.pop(k // fact)
			if not nums:
				return result
			k %= fact
			fact //= len(nums)
		return result


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		import itertools
		li = []
		for i in range(1, n + 1):
			li.append(str(i))
		permut = itertools.permutations(li)
		i = 0
		for p in permut:
			i += 1
			if i == k:
				return ''.join(p)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		arr = list(range(1, n + 1))
		result = []
		self.find_kth_permutation(arr, k, result)
		return ''.join(result)

	def find_kth_permutation(self, arr, k, ans):
		if not arr:
			return
		a = len(arr)
		cnt = self.factorial(a - 1)
		select = (k - 1) // cnt
		ans += str(arr[select])
		del arr[select]
		k = k - cnt * select
		self.find_kth_permutation(arr, k, ans)

	def factorial(self, n):
		if n == 0 or n == 1:
			return 1
		return n * self.factorial(n - 1)


from typing import List
import math

class Solution:

	def __init__(self):
		self.res = 0
		self.rem = 0

	def helper(self, digits, ans, sub, visited):
		if len(sub) == len(digits):
			self.rem -= 1
			if self.rem == 0:
				self.res = int(''.join(sub))
			return
		for j in range(len(digits)):
			if self.rem == 0:
				return
			if not visited[j]:
				visited[j] = True
				sub.append(digits[j])
				self.helper(digits, ans, sub, visited)
				visited[j] = False
				sub.pop()
		return

	def kthPermutation(self, n: int, k: int) -> str:
		factor = math.factorial(n - 1)
		k -= 1
		ans = []
		numbers_left = list(range(1, n + 1))
		for m in range(n - 1, 0, -1):
			index = int(k // factor)
			ans += str(numbers_left[index])
			numbers_left.pop(index)
			k %= factor
			factor /= m
		ans += str(numbers_left[0])
		return ''.join(ans)


from typing import List
from itertools import permutations
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		(l, s) = ([str(i) for i in range(1, n + 1)], '')
		while n > 0:
			f = math.factorial(n - 1)
			index = (k - 1) // f
			s += l.pop(index)
			n -= 1
			k %= f
		return s


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		arr = [i + 1 for i in range(n)]
		ans = ''
		k -= 1
		factorials = [1 for i in range(n)]
		for i in range(1, n):
			factorials[i] = factorials[i - 1] * i
		for i in range(n):
			idx = int(k / factorials[n - i - 1])
			k = k % factorials[n - i - 1]
			digit = str(arr[idx])
			ans += digit
			arr.pop(idx)
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:

		def solve(f, k, d):
			if d == 0:
				ans.append(str(p[k // f]))
				return
			ans.append(str(p[k // f]))
			p.remove(p[k // f])
			k = k % f
			f = f // d
			d -= 1
			solve(f, k, d)
		k -= 1
		ans = []
		p = [i for i in range(1, n + 1)]
		f = 1
		for i in range(1, n):
			f *= i
		solve(f, k, n - 1)
		return int(''.join(ans))


from typing import List

def factorial(i):
	if i <= 1:
		return 1
	return i * factorial(i - 1)

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		ans = ''
		word = [i for i in range(1, n + 1)]
		k -= 1
		while True:
			x = factorial(n - 1)
			bucket = k // x
			ans += str(word.pop(bucket))
			if len(word) == 0:
				break
			k = k % x
			n -= 1
		return ans


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		k = k - 1
		a = [i + 1 for i in range(n)]
		ans = []
		while a:
			f = math.factorial(n - 1)
			p = int(k / f)
			ans.append(a.pop(p))
			n -= 1
			k = k % f
		s = ''
		for i in ans:
			s += str(i)
		return s


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		num = []
		for i in range(1, n):
			fact = fact * i
			num.append(i)
		num.append(n)
		k -= 1
		ans = ''
		while True:
			ans += str(num[k // fact])
			num.pop(k // fact)
			if len(num) == 0:
				break
			k = k % fact
			fact = fact // len(num)
		return ans

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		obj = Solution()
		res = obj.kthPermutation(a[0], a[1])
		print(res)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		arr = list(range(1, n + 1))
		result = []
		self.find_kth_permutation(arr, k, result)
		return ''.join(result)

	def find_kth_permutation(self, arr, k, ans):
		if not arr:
			return
		a = len(arr)
		cnt = self.factorial(a - 1)
		select = (k - 1) // cnt
		ans += str(arr[select])
		del arr[select]
		k = k - cnt * select
		self.find_kth_permutation(arr, k, ans)

	def factorial(self, n):
		if n == 0 or n == 1:
			return 1
		return n * self.factorial(n - 1)

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		obj = Solution()
		res = obj.kthPermutation(a[0], a[1])
		print(res)


from typing import List

class Solution:

	def fact(self, n):
		if n == 0 or n == 1:
			return 1
		return n * self.fact(n - 1)

	def kthPermutation(self, n: int, k: int) -> str:
		ans = ''
		my_nums = [x for x in range(1, n + 1)]
		k -= 1
		while len(my_nums):
			fact = self.fact(len(my_nums) - 1)
			index = int(k / fact)
			ans += str(my_nums[index])
			k %= fact
			my_nums.pop(index)
		return ans


from typing import List

def fact(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		k -= 1
		l = [str(i + 1) for i in range(n)]
		i = 0
		while k > 0:
			x = fact(n - i - 1)
			y = 0
			j = i
			while k >= y + x:
				y += x
				j += 1
			(l[i], l[j]) = (l[j], l[i])
			l[i + 1:] = sorted(l[i + 1:])
			k -= y
			i += 1
		return ''.join(l)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = [0] * (n + 1)
		fact[0] = 1
		s = ''
		for i in range(1, n + 1):
			fact[i] = fact[i - 1] * i
			s += str(i)
		ans = ''
		k -= 1
		ind = n - 1
		while ind >= 0:
			t = k // fact[ind]
			ans += s[t]
			k = k % fact[ind]
			ind -= 1
			s = s[:t] + s[t + 1:]
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		digits = []
		fact = 1
		for i in range(1, n):
			fact *= i
			digits.append(i)
		digits.append(n)
		k = k - 1
		res = ''
		while True:
			index = k // fact
			res += str(digits[index])
			del digits[index]
			if len(digits) == 0:
				break
			k = k % fact
			fact = fact // len(digits)
		return res


from typing import List

class Solution:

	def solve(self, n, number, k):
		ans = ''
		fact = 1
		for i in range(1, n):
			fact = fact * i
		while True:
			ans = ans + str(number[int(k // fact)])
			del number[int(k // fact)]
			if len(number) == 0:
				break
			k = k % fact
			fact = fact // len(number)
		return ans

	def kthPermutation(self, n: int, k: int) -> str:
		number = []
		for i in range(1, n + 1):
			number.append(i)
		ans = self.solve(n, number, k - 1)
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		k -= 1
		fact = [1 for i in range(n + 1)]
		for i in range(1, len(fact)):
			fact[i] = fact[i - 1] * i
		arr = []
		for i in range(n):
			arr.append(i + 1)
		res = ''
		visited = [False for i in range(len(arr))]
		while n >= 1:
			val = fact[n - 1]
			(q, k) = divmod(k, val)
			curr = 0
			for i in range(len(arr)):
				if not visited[i]:
					curr += 1
				if curr == q + 1:
					visited[i] = True
					res += str(arr[i])
					break
			n -= 1
		return res


from typing import List
import math

class Solution:

	def __init__(self):
		self.res = set()

	def kthPermutation(self, n: int, k: int) -> str:
		a = []
		for i in range(1, n + 1):
			a.append(str(i))

		def f(a, k, n, ans):
			if len(a) == 1:
				ans += a[0]
				return ans
			index = k // math.factorial(n - 1)
			if k % math.factorial(n - 1) == 0:
				index -= 1
			ans += a[index]
			a.pop(index)
			k = k - math.factorial(n - 1) * index
			return f(a, k, n - 1, ans)
		return f(a, k, n, '')


from typing import List

class Solution:

	def fact(self, n):
		ans = 1
		for i in range(1, n + 1):
			ans *= i
		return ans

	def kthPermutation(self, n: int, k: int) -> str:
		if n == 1:
			return str(k)
		each = self.fact(n - 1)
		number = (k - 1) // each + 1
		l = []
		for i in range(1, n + 1):
			if i != number:
				l.append(i)
		ans = str(number)
		nx = (k - 1) % each
		small = self.kthPermutation(n - 1, nx + 1)
		for i in small:
			ans += str(l[int(i) - 1])
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		nums = [_ for _ in range(1, n + 1)]
		res = []
		self.solve(nums, res, k)
		return ''.join([_ for _ in res])

	def solve(self, nums, res, k):
		if not nums:
			return
		N = len(nums)
		cnt = self.factorial(N - 1)
		select = (k - 1) // cnt
		res += str(nums[select])
		del nums[select]
		k = k - select * cnt
		self.solve(nums, res, k)

	def factorial(self, N):
		if N == 0 or N == 1:
			return 1
		return N * self.factorial(N - 1)


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		a = [str(i) for i in range(1, n + 1)]
		ans = []
		self.func(n, a, k - 1, ans)
		return ''.join(ans)

	def func(self, n, a, k, ans):
		if n == 1:
			ans.append(a[0])
			return
		x = math.factorial(n - 1)
		ans.append(a[k // x])
		a.remove(a[k // x])
		self.func(n - 1, a, k % x, ans)


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		fact = 1
		numbers = [x for x in range(1, n + 1)]
		for i in range(1, n):
			fact = fact * i
		k = k - 1
		ans = ''
		while True:
			ans = ans + str(numbers[k // fact])
			del numbers[k // fact]
			if numbers == []:
				break
			k = k % fact
			fact = fact // len(numbers)
		return ans


from typing import List
import math

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:
		s = list(map(str, range(1, n + 1)))
		D = ''.join(s)
		farr = [1]
		for i in range(1, n):
			farr.append(i * farr[-1])
		ans = ''
		for i in range(n):
			d = math.ceil(k / farr[n - i - 1])
			ans += D[d - 1]
			D = D.replace(D[d - 1], '')
			k = k % farr[n - i - 1]
		return ans


from typing import List

class Solution:

	def kthPermutation(self, n: int, k: int) -> str:

		def fact(n):
			p = 1
			for j in range(1, n + 1):
				p *= j
			return p
		rem = k - 1
		lst = []
		ans = ''
		for j in range(1, n + 1):
			lst.append(j)
		l = n
		while lst != []:
			a = fact(l - 1)
			q = rem // a
			rem = rem % a
			ele = lst[q]
			lst.pop(q)
			ans += str(ele)
			l -= 1
		return ans