Greedy Approach 
IntuitionIf n is even, we can either start with an even number or an odd number.
If n is odd, we have to start with the parity that appears more frequently (sin
# Intuition
If n is even, we can either start with an even number or an odd number.
If n is odd, we have to start with the parity that appears more frequently (since one group will have one extra element).
Just try some cases to see how the ordering works out.
# Approach
Use combinatorics to determine which number will be first by calculating the number of permutations that can be formed with the remaining numbers. At each step:

* Compute the number of arrangements available if a certain candidate is chosen as the next number (using factorial calculations for the remaining even and odd numbers).

* Accumulate these counts and compare with the target k to decide if the current candidate should be chosen.
* Once the candidate is chosen, remove it from the available set (even or odd) and proceed with the next step.

* Special handling is applied when n≥24 to fix a prefix and avoid computing huge factorials, thereby reducing the problem to a manageable size. simply add x(1,2...) till untill n-x <= 22
# Complexity
- Time complexity:
O(n^3) for small n
- Space complexity:
O(n) space

# Code
```cpp []
class Solution 
{
public:
    long long fact(long long x)
    {
        if (x <= 1) return 1;
        return x * fact(x - 1);
    }
    
    vector<int> permute(int n, long long k) 
    {
        set<int> even, odd;
        for (int i = n; i >= 1; i--)
        {
            if (i % 2 == 0)
                even.insert(i);
            else
                odd.insert(i);
        }
        
        vector<int> ret;
        long long ans = 0;
        
        if(n>=24)
        {
            int x = 0;
            for(int i=1;i<=n;i++)
            {
                if(n-x<=22)
                {
                    break;
                }
                ret.push_back(i);
                if(i%2==0)
                {
                    even.erase(i);
                }
                else
                {
                    odd.erase(i);
                }
                x++;
            }   
        }
        else if(n%2==0)
        {

        long long o = fact(even.size() - 1) * fact(odd.size());
        long long e = fact(odd.size() - 1) * fact(even.size());
        for (int i = 1; i <= n; i++)
        {
            //cout<<ans<<endl;
            if (ret.empty())
            {
                if (i % 2 == 0)
                {   
                    if (ans + o >= k)
                    {
                        ret.push_back(i);
                        even.erase(i);
                        break;
                    }
                    ans += o;
                }
                else
                {
                    if (ans + e >= k)
                    {
                        ret.push_back(i);
                        odd.erase(i);
                        break;
                    }
                    ans += e;
                }
            }
        }
        }
        else
        {
            if(odd.size()>even.size())
            {
                long long o = fact(even.size() - 1) * fact(odd.size());
                long long e = fact(odd.size() - 1) * fact(even.size());
                for (int i = 1; i <= n; i+=2)
                {
                    if (ret.empty())
                    {
                        if (i % 2 == 0)
                        {   
                            if (ans + o >= k)
                            {
                                ret.push_back(i);
                                even.erase(i);
                                break;
                            }
                            ans += o;
                        }
                        else
                        {
                            if (ans + e >= k)
                            {
                                ret.push_back(i);
                                odd.erase(i);
                                break;
                            }
                            ans += e;
                        }
                    }
                }
            }
            else
            {
                long long o = fact(even.size() - 1) * fact(odd.size());
                long long e = fact(odd.size() - 1) * fact(even.size());
                for (int i = 2; i <= n; i+=2)
                {
                    if (ret.empty())
                    {
                        if (i % 2 == 0)
                        {   
                            if (ans + o >= k)
                            {
                                ret.push_back(i);
                                even.erase(i);
                                break;
                            }
                            ans += o;
                        }
                        else
                        {
                            if (ans + e >= k)
                            {
                                ret.push_back(i);
                                odd.erase(i);
                                break;
                            }
                            ans += e;
                        }
                    }
                }
            }
        }
        if(ret.empty()) return ret;
        for (int i = 0; i < n - 1; i++)
        {
            if (ret.back() % 2 == 0)
            {
                if (odd.empty()) break;
                long long o = + fact(odd.size() - 1) * fact(even.size());
                for (auto p : odd)
                {
                    if (ans + o  >= k)
                    {
                        ret.push_back(p);
                        odd.erase(p);
                        break;
                    }
                    ans += o;
                }
            }
            else
            {
                if (even.empty()) break;
                long long e = fact(even.size() - 1) * fact(odd.size());
                for (auto p : even)
                {
                    if (ans + e >= k)
                    {
                        ret.push_back(p);
                        even.erase(p);
                        break;
                    }
                    ans += e;
                }
            }
        }
        
        return ret;
    }
};
```
['C++']