[Python] Short & Clean Solution With Well Commented Code And Explanation
IntuitionApproachFirst do some maths to find out the total number of possible permutations. If k > perms, can return empty list. Intuition for the math here:
wh
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->


# Approach
<!-- Describe your approach to solving the problem. -->
First do some maths to find out the total number of possible permutations. If k > perms, can return empty list. Intuition for the math here:
- when n odd, we know first elem is odd (and therefore 3rd and 5th elem). We have ceil(n/2) options for the first odd number (since ceil(n/2) odd nums), ceil(n/2)-1 for the second odd, etc. Similar logic for even, except we have n//2 even numbers so it's factorial(n//2)
- when n even, we know half of the options will start with even, and half options will start with odd. Let's assume first num is even, there are n//2 options for the first num, also n//2 options for second num which is odd, n//2-1 options for third num which is even, etc.

Then, think of it like this: we want to build our solution res array one element at a time. We know the result must be alternating, ex. if current element is even, next will be odd, we track this using a single variable `cur`.

The hardest part is figuring out at current iteration, which number to place? For this, I just built a large enough example and thought through the math.

The "edge" case we consider is when n is even, the first number can be either even or odd, hence the if-else statement before the for-loop.

```
        n = 5
        1,2,3,4,5
        1,2,5,4,3
        1,4,3,2,5
        1,4,5,2,3
        3,2,1,4,5
        3,2,5,4,1
        3,4,1,2,5
        3,4,5,2,1
        5,2,1,4,3
        5,2,3,4,1
        5,4,1,2,3
        5,4,3,2,1
```

# Complexity
- Time complexity:
O(n^2)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        perms = 0
        # some math to calculate total num of permutations
        if n % 2 == 0:
            perms = factorial(n//2) * factorial(n//2) * 2
        else:
            perms = factorial(ceil(n/2)) * factorial(n//2)

        if k > perms:
            return []

        r1 = [] # odd numbers, ex. [1,3,5]
        r2 = [] # even numbers, ex. [2,4]
        for i in range(1, n+1):
            if i % 2 == 0:
                r2.append(i)
            else:
                r1.append(i)

        res = []
        count = n
        cur = -1 # currently, do we have to add an even number or odd number?
        if n % 2 == 0:
            # first element is unique since can be even or odd (later, even and odd must alternate)
            count -= 1
            num_per_p = perms // n
            num = ceil(k / num_per_p)
            
            k = k % num_per_p
            perms //= n
            
            res.append(num)
            if num % 2 == 0:
                r2.remove(num)
                cur = 1
            else:
                r1.remove(num)
                cur = 2
        else:
            # first number has to be odd
            cur = 1

        for _ in range(count):
            # figure out i where we remove i-th number from either r1 or r2
            L = len(r1) if cur == 1 else len(r2) # 3
            i = ceil(k / (perms // L))

            # update k, perms
            k = k % (perms // L)
            perms //= L

            if cur == 1:
                res.append(r1[i-1]) # i is 1-indexed
                r1.remove(r1[i-1])
                cur = 2 # always alternate between even and odd
            else:
                res.append(r2[i-1])
                r2.remove(r2[i-1])
                cur = 1

        return res
```
['Python3']