100% beats! 12 ms runtime, done using maths.
Intuitionhere i have used mathematics to compute the possible number of permutation for any starting number with any number of digits after itApproachsee for 1,
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
here i have used mathematics to compute the possible number of permutation for any starting number with any number of digits after it

# Approach
<!-- Describe your approach to solving the problem. -->
see for 1, 2, 3, 4, 5, 6, 7 you can only shuffle even with even and odd with odd you can change even with odd. also for odd n you cannot start the sequence with a even number, considering the above condition in addition to availability of the number i checked if i can use the number on ith position to generate the permutation,

if generate permutation are lesser then k reduce k by no of permutation and move to next value and if greater or equal add it in result and decrease the i and other variables too.


important thing computing factorial here was a hectic task, it keep overflowing for higher number even after using long and double so i use BigInteger and it worked and also to prevent compution of factorial again and again i used hashMap to memoize the results.

# 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
```java []

import java.math.BigInteger;
class Solution {
    // int count = 0;
    // public void helper(int[] nums,int idx, boolean[] freq, long k){
    //     if(idx == nums.length){
    //         count++;
    //         return ;
    //     }

    //     for(int i=1; i<freq.length; i++){
    //         if (!freq[i] && (idx == 0 || (i + nums[idx - 1]) % 2 == 1)){
    //             freq[i] = true;
    //             nums[idx] = i;
    //             helper(nums, idx+1, freq, k);
    //             if(count == k)
    //                 return;
    //             freq[i] = false;
    //             nums[idx] = 0;
    //         }
    //     }
    // }






    private HashMap<Integer, BigInteger> factMemo = new HashMap<>();

    public BigInteger fact(int n) {
        if (n <= 1) return BigInteger.ONE;
        if (factMemo.containsKey(n)) return factMemo.get(n);
        BigInteger res = BigInteger.valueOf(n).multiply(fact(n - 1));
        factMemo.put(n, res);
        return res;
    }

    public int[] permute(int n, long k) {
        int[] res = new int[n];
        int idx = 0;
        boolean[] available = new boolean[n + 1];
        int even = n / 2, odd = (n + 1) / 2;
        int prev = 0, count = n;
        
        while (count > 0) {
            int num = 1;
            boolean selected = false;
            
            while (!selected && num <= n) {
                if (!available[num] && (prev == 0 || (prev + num) % 2 == 1) && (num % 2 == 0 ? even >= odd : even <= odd)) {
                    BigInteger total = fact(count / 2).multiply(fact((count - 1) / 2));
                    
                    if (BigInteger.valueOf(k).compareTo(total) > 0) {
                        k -= total.longValue();
                    } else {
                        prev = num;
                        available[num] = true;
                        selected = true;
                        if (num % 2 == 0) even--;
                        else odd--;
                        res[idx++] = num;
                    }
                }
                num++;
            }
            
            if (!selected) return new int[]{};
            count--;
        }
    
        return res;
    }



}
```
if you have any doubt or suggestion regarding the code then do comment it and if you like the solution the do upvote it.
['Math', 'Java']