[0 ms] [Beats 100% 🔥] Python solution (Take advantage of small `k`!)
ApproachCalculate the total number of permutations, use totalk​ to calculate the digit in first position, then iterate on the subproblem.Complexity
Time complex
![image.png](https://assets.leetcode.com/users/images/44222c0b-c20c-4ce8-9eb4-ba01df564baf_1742229034.0671682.png)

# Approach
Calculate the total number of permutations, use $$\frac{k}{total}$$ to calculate the digit in first position, then iterate on the subproblem.

# Complexity
- Time complexity is $$O(1)$$ since  $$k \le 10^{15}$$, implying we only need to iterate on the $$n \le 23$$ subproblem (the $$n-23$$ prefix of the permutation will just be `[1, 2, 3, 4, 5, ...]`)
  - As an analogy, imagine you could only look up the first 100 words in an english dictionary. You would only find words starting with `a`. Now, note that the number of valid permutations for $$n=69$$ is greater than $$10^{78}$$, which is astronomically larger than the bound on $$k$$. The size of the sorted "dictionary" is so large that you'd only find "words" starting with `aaaaa...`

# Code
```python3 []
def permute(n: int, k: int):
  if n <= 23:
    base = 1
    answer = []
  else:
    # we can skip many prefix elements because k is small
    base = n - 23 + 1
    answer = list(range(1, base))
    n = 23

  # even case is weird because first element can be either parity, handle the first element now
  if n % 2 == 0:
    total_perms = n // 2 * math.factorial(n // 2 - 1) ** 2
    if k // total_perms >= n: return []
    answer.append(k // total_perms + base)
    parity = 1 - k // total_perms % 2
    digits = {
      0: [i for i in range(0, n, 2) if i != k // total_perms],
      1: [i for i in range(1, n, 2) if i != k // total_perms],
    }
    k %= total_perms
  else:
    total_perms = (n // 2 + 1) * math.factorial(n // 2) ** 2
    if k >= total_perms: return []
    parity = 0
    digits = { 0: list(range(0, n, 2)), 1: list(range(1, n, 2)) }

  # now we know which parities and digits remain for the rest of the permutation
  for _ in range(len(digits[0]) + len(digits[1])):
    total_perms //= len(digits[parity])
    answer.append(digits[parity].pop(k // total_perms) + base)
    k %= total_perms
    parity = 1 - parity
  return answer

class Solution:
  @staticmethod
  def permute(n, k): return permute(n, k - 1)

```
['Math', 'Combinatorics', 'Python3']