Skip to content

3470. Permutations IV 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def permute(self, n: int, k: int) -> list[int]:
    ans = []
    isLookingForEven = True
    remainingNumbers = list(range(1, n + 1))

    for turn in range(n):
      remainingPermutations = (math.factorial((n - 1 - turn) // 2) *
                               math.factorial((n - turn) // 2))
      found = False
      for index, number in enumerate(remainingNumbers):
        if number % 2 != isLookingForEven and (turn > 0 or n % 2 == 1):
          continue
        if k <= remainingPermutations:
          ans.append(remainingNumbers.pop(index))
          isLookingForEven = ans[-1] % 2 == 0
          found = True
          break
        k -= remainingPermutations
      if not found:
        return []

    return ans