✅EASY 100% BEATS ||💡EXPLAIN FOR BEGINNERS || NO DP || DIGITS CHECKING
IntuitionThe intitution is simply check what more possible combinations i can generate after the current index, it will help us to predict the current index val
# Intuition
The intitution is simply check what more possible combinations i can generate after the current index, it will help us to predict the current index value.

# Approach
firstly find out the index after which we will have atleast k possible combinations so that we can directly assign the values till this index and this also avoids overflow while counting the total possible permutations.
now for every index simply check that amongst the possible numbers which count of number we have to use (ex: we have possiblity of evens say 2,4,6,8. so for count 4 i mean the number 8). the odd and even can be checked by checking the parity of 1st number in the required permutation. now simply count for the required number of that parity which is not present previously.
check the code for more explanation

# Complexity
- Time complexity:
n + n*n/2
O(n^2)

- Space complexity:
O(n) just to check the already used numbers
suggestion: use bitset for optimised space

# Code
```cpp []
#define ll long long
class Solution {
public:
    vector<int> permute(int n, long long k) {
        ll temp=1;
        ll ct=2;
        int ind=0;
        // count the total number of permutaion we can have 
        for(int i=n;i>=1;i--)
        {
            if(temp>=k){
                ind=i; // after this index we will have atleast k per poss.
                break; // break to avoid overflow of total permutation cnt.
            }
            if(i==1)
            {
                if(n&1)      // if n is odd then we can't have even numbers
                temp*=((n+1)/2);  // at the first index
                else
                temp*=n;
            }
            else
            temp*=(ct/2); // every index we we (n-i)/2 options as
            ct++;         // either even or odd.
        }
        if(temp<k) return {};  // kth permutation doesn't exists.
        bitset<100+1> mp;
        vector<int> ans;
        for(int i=1;i<=ind;i++)
        {                          // allot direct values after which
            ans.push_back(i);      // atleast k permutation are possible.
            mp[i]=1;
        }
        for(int i=ind+1;i<=n;i++)
        {
            if(i==1)
            {
                if(n&1)
                temp/=((n+1)/2);
                else
                temp/=n;
            }
            else
            temp/=((n-i+2)/2); // temp after division gives us the number
            ll tt=k/temp;      //of combinations possible after this index.
            if(k%temp!=0)
            tt++;              // tt is the number of value which will be
            k-=((tt-1)*temp);  // here amongst the possible values at this
            if(i==1)           // index. and k is the left amount of perm.
            {
                if(n&1)
                tt=2*tt-1;
                ans.push_back(tt);
                mp[tt]=1;
            }
            else
            {
                int par=1;
                if(ans[0]%2==0)
                par=2;             // check the parity of first index
                if(n&1)
                par=1;              // if n is off can't have even value.
                if((i-1)&1)
                {
                    if(par==1)
                    par=2;
                    else
                    par=1;
                }                   // check parity at required index.
                int ct1=1;
                for(int j=par;;j+=2)
                {
                    if(mp[j]) continue;  // is already present then skip.
                    if(ct1==tt)
                    {
                        ans.push_back(j);
                        mp[j]=1;
                        break;        // find the tt value and assign.
                    }
                    ct1++;
                }
            }
        }
        return ans;
    }
};
```
# Please upvote if you find helpful and intutive. ask if you have any doubt.
['Array', 'Hash Table', 'Combinatorics', 'C++']