O(n^3) time and O(n) extra space- with comment c++ code 
IntuitionApproachComplexity
Time complexity: O(n^3)

Space complexity:O(n)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
class Solution {
public:
    vector<int> permute(int n, long long k) {
        vector<int>ans(n);
        long long count =0;//count till now before choosing a value at index i
        vector<int>vis(n+1,0);
        for(int i=0;i<n;i++)//fill ans one by one
        {
            for(int j=1;j<=n;j++)// choose j to be filled at index i
            {
                if(i==0 && n%2 && j%2==0) continue;//if size odd dont start with even value
                if(!vis[j]){ //if j is not aleardy filled in the array
                    if(i==0 || ans[i-1]%2!=j%2) //j is not same type of previous element in ans
                    {
                        //if you choose j at index i how many further combinations can be posible
                        //n=100, j=1 at  i=0 then from i=1 onward - total =  50*49*49*48*48...

                        //calculate for one type (odd/even)
                        //n=100 and j=2 at i=0 then from i=2 onward - even combin = 49*48*...
                        long long mul =1;
                        for(int c = (n+j%2)/2-(i+2)/2;c>0;c--){
                            mul*=c;
                            if(count+mul>=k)// if total count exceeds that means ans is within the range , no need to calcuate further
                            {
                                break;
                            }
                        }
                        if(count+mul>=k)// you can take j at i index
                        {
                                ans[i]=j;
                                vis[j]=1;
                                break;
                        }

                        //calculate for another type(odd/even)
                        //n=100 and j=2 at i=0 then from i=1 onward - odd combin = 50*49*48*...
                        for(int c = (n+(j%2==0))/2-(i+1)/2;c>0;c--){
                            mul*=c;
                            if(count+mul>=k){
                                break;
                            }
                        }
                        if(count+mul>=k){
                                ans[i]=j;
                                vis[j]=1;
                                break;
                        }

                        if(!vis[j])//if still total<k the choose next j
                        {
                            count+=mul;
                        }
                    }
                }
                if(ans[i]!=0) break;
            }
            if(ans[i]==0) return {};
        }
        return ans;
    }
};

```
['C++']