Golang solution o(n)
IntuitionApproachSplit odds/evens numbers. Swap them on each iteration.
Calculate combination count based on number of odds and evens which is not used. Find va
# Intuition

<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
Split odds/evens numbers. Swap them on each iteration.
Calculate combination count based on number of odds and evens which is not used. Find value to use based on k an combination count after current number.


Combinations count maybe too big number (13!*12! > 10^15) - in this case just need to use first value from remainig numbers.

Select starting list for even n is a little bit tricky. Need to find which number (odd or even) will be first in the result. And after process with opposite list.
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```golang []
func permute(n int, k int64) []int {
    // need idx instead of value
    k--
    
    // 12 is enougth, because 13! * 12! > 10^15
    factors := factorial(12)
    result := []int{}
    var fn func(cur []int, next []int, k int64)
    // current - list of unsued numbers which should be used on the current step
    // next - list of unused numbers for next step
    // swap odds/evens on next call
    fn = func(current []int, next []int, k int64) {
        if len(current) == 0 {
            return
        }

        // number of combinations greater than 10^15, just use next value
        if len(current) >= 13 || len(next) >= 13 {
            // just add next value from
            result = append(result, current[0])
            fn(next, current[1:], k)
            return
        }

        // calculate count of combination after current step
        nextCombinationCnt := factors[len(current)-1] * factors[len(next)]
        // find needed index to result
        idx := int(k/nextCombinationCnt)
        // add result
        result = append(result, current[idx])
        // remove used number
        nextCurrent := append(current[:idx], current[idx+1:]...)
        // generate further - swap odds/evens and use remaing part of k
        fn(next, nextCurrent, k-int64(idx)*nextCombinationCnt)
    }
    
    odds, evens := oddsEvensExclude(n, 0)
    if len(odds) >= 13 || len(evens) >= 13 {
        // big number, always start with 1, 2...
        fn(odds, evens, k)
    } else if n & 1 == 1 {
        // n is odd, so start with odd
        // check that there enouth combination to fit k
        if k > 0 && factors[len(odds)]*factors[len(evens)] <= k {
            return nil
        }
        fn(odds, evens, k)
    } else {
        // n is even
        combs := factors[len(odds)]*factors[len(evens)-1]
        // check that there enouth combination to fit k ( n*(n/2)!*(n-1)! )
        if int64(n) * combs <= k {
            return nil
        }

        // find start number
        div := int(k / combs)
        use := div+1
        // add start value to result
        result = append(result, use)
        // exclude used value in odds|evens
        odds, evens := oddsEvensExclude(n, use)
        // start by odds|evens, based on used number
        if use & 1 == 1 {
            fn(evens, odds, k-int64(div)*combs)
        } else {
            fn(odds, evens, k-int64(div)*combs)
        }
    }

    return result
}

func factorial(n int) []int64 {
    res := make([]int64, n+1)
    res[0] = 1
    for i := 1; i <= n; i++ {
        res[i] = res[i-1]*int64(i)
    }
    return res
}

func oddsEvensExclude(n int, exclude int) ([]int, []int) {
    odds, evens := []int{}, []int{}
    for i := 1; i <= n; i++ {
        if i == exclude {
            continue
        }
        if i & 1 == 1 {
            odds = append(odds, i)
        } else {
            evens = append(evens, i)
        }
    }
    return odds, evens
}
```
['Go']