✅Brute force + simple ad-hoc math calculations C++ code
IntuitionFind k-th alternating permutation A, such that A is a permutation of values from 1 to n, no two adjacent elements are both odd or even, n ranges from 1
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Find **k**-th alternating permutation **A**, such that **A** is a permutation of values from 1 to n, no two adjacent elements are both odd or even, n ranges from 1 to 100 only, so apply brute-force looping to solve it. 

Here are 5 observations which lead to the looping solution:

* Starting value
* Values after the starting value
* Total number of arrangements using available numbers
* Partitioning the array A
* Relative position in array A with reference to k

### Observation 1: Starting value
* If n is odd: The starting value must be odd.

Reason: Let **O** = odd number, **E** = even number, **_**(underscore) = empty slot.

e.g. n=7, arrangement of values **must be**:
[O,E,O,E,O,E,O]

If starting value is E:
[E, _E, _E, _]

There are only 3 empty slots, which is not enough to place 4 odd numbers.

* If n is even: The starting value can be either odd or even.

Reason: There are same number of odd and even values in the array, which is n/2 for each. After placing either 1 odd or 1 even value to the start, there are n/2-1 odd/even numbers left, and n/2 even/odd numbers left. There are n/2 slots associated with n/2 even/odd numbers, it is enough to contain n/2-1 odd/even numbers. 

### Observation 2: Values after the starting value
* The parity of integer after the starting value (A[i], i>0) must depends on the value before it (A[i-1])

Reason: The question stated that we need to find the k-th alternating permutation... see the definitions.
### Observation 3: Total number of arrangements using available numbers in array A
##### Observation 3.1: Total number of arrangements after assigning the starting value  
***Case 1**: n is odd, assigning starting value*

* There are ceil(n/2) odd numbers to choose from. You must assign an odd number only to the start (refer to observation 1)
* There are ceil(n/2)-1=floor(n/2) odd numbers left, and floor(n/2) even numbers left. 
* Each number in the array **A** is unique (refer to question statement)
* Slots for odd numbers and even numbers are fixed (refer to observation 1) 
* Therefore, there are $$floor(n/2)!$$ ways to assign odd numbers to remaining slots for odd numbers, and $$floor(n/2)!$$ ways to assign even numbers to remaining slots for even numbers.


***Case 2**: n is even, assigning starting value*
* You can select either odd or even number for the starting value.
* There are $$(n/2-1)!$$ ways to assign values with the same parity as the starting value into n/2-1 slots, and $$(n/2)!$$ ways to assign values with their parity differs from the starting value into n/2 slots.

##### Observation 3.2: A matter of perspective on treating the permutation of values in array A
What if A is empty now, how many possible valid permutations can be generated?

**Case 1: n is odd**: Slots are fixed, so there are $$ceil(n/2)!\times floor(n/2)!$$ possible permutations.

**Case 2: n is even**: The parity arrangement of values can be either O E O E... or E O E O..., i.e. there are two possible parity arrangements. So, there are $$(n/2)! \times (n/2)! \times 2$$ possible permutations.

When combined with observation 3.1, we notice that: 
**Case 1: n is odd**:
The starting value must be odd. Therefore, there are ceil(n/2) possible starting values. $$ceil(n/2)!\times floor(n/2)!$$ can be re-written as $$=ceil(n/2)\times floor(n/2)!\times floor(n/2)!$$

$$floor(n/2)!\times floor(n/2)!$$ aligns with observation 3.1.
**Case 2: n is even**:
The starting value can be either odd or even. Therefore, there are n possible starting values. $$n/2! \times n/2! \times 2$$ can be re-written as $$=n \times (n/2-1)! \times n/2!$$

$$(n/2-1)! \times n/2!$$ aligns with observation 3.1.
##### Observation 3.3: General method to check for number of possible permutation(s) after assigning first m values

Let v = minimum(count of remaining odd values, count of remaining even values).

The value will be either $$v! \times v!$$ or $$(v-1)! \times v!$$

### Observation 4: Partitioning the array A
We need to find the k-th valid permutation **ordered lexicographically.**

Let a "round" refers to assigning one value into the resultant array with index from 0 to n-1. 

For each round, we have a list of unassigned, possible values, which are: 

**Case 1: at the start**: refer to observation 1.
**Case 2: after the start**: Values which: 
1. Aligns with the parity of the location (refer to observation 2), and
2. are available for assignment

Order those values in ascending order.

Based on observation 3, you can calculate the total number of possible permutations after placing the current value.

You will notice the following:

e.g. n=6, at the start. Number of possible permutations after the start = 3!*2! = 12. There are 6 possible starting values.

|Possible value|Partition|
|--|--|
|1|1 to 12|
|2|13 to 24|
|3|25 to 36|
|4|37 to 48|
|5|49 to 60|
|6|61 to 72|

This means, if the starting value is 4, for example, the resultant array can represent the 37th to 48th possible permutation, aha ha ha ha... (-_-) 

### Observation 5: Relative position in array A with reference to k

Of course, you should update the value k. 

If the partition size is >=k, then no need to adjust k. Assign whatever value that is, move to the next slot in the next round (refer to observation 4)

If the partition size is <k, then find the partition which covers k, aha ha ha ha... (-_-) simple right?

For example, n=6, at the start, and k=56, find the 56th permutation.

|Possible value|Partition|
|--|--|
|1|1 to 12|
|2|13 to 24|
|3|25 to 36|
|4|37 to 48|
|5|49 to 60|
|6|61 to 72|

You assign 5 to the start. 56 in range [49,60] is relative to 8 in range [1,12]. Change k to 8. 

In the next round, calculate partition size, and assign the next value accordingly. 

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

Directly implement this simple idea using brute-force method. 

## Thoughts and feelings

Questions like this is just a test on working memory more than about IQ and I am lacking both IQ and working memory of course (-_-) that's why I am here, just hoping that I could improve a bit... my brain size does become larger physically, but it is far from enough to solve hard problems... it is better late than never I guess. 

What's magical about LeetCode is that, every time you have solved a problem, you have actually learnt nothing out of it. It is not some wisdom told by some wise elders, just a bunch of observations. Despite everyone can follow someone else's observations, not everyone can find them independently. I am barely average, as supported by public exam results, contest rankings, etc., and I am just wondering why such a huge cognitive difference exists among humans. It is discouraging, as if someone like me can never change my own destiny. 

## Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$~O(n^2)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$~O(n)$$
# Code
```cpp []
typedef long long int lld;
class Solution {
public:
    lld F[20]; bool U[101]; int VC[2];
    double calLog10Sum(vector<int>& candidates) {
        double log10sum=0.00;
        for (int c:candidates) {
            log10sum=log10sum+std::log10(F[c]);
        }
        return log10sum;
    }
    bool isOverflow(vector<int> candidates, lld flag) {
        for (int c:candidates) { if (c>=18) return true; }
        double log10sum=calLog10Sum(candidates); 
        double log10sumflag=std::log10(flag);
        return ((log10sum-log10sumflag)>=1e-10)?true:false;
    }
    void initCurval(vector<int>& v, int pp, int n) {
        memset(VC,0,sizeof(VC));
        for (int i=1; i<=n; i++) {
            if (!U[i]&&(pp==-1||(i&1)==pp)) {v.push_back(i);}
            if (!U[i]) {VC[(i&1)]++;}
        }
        return;
    }
    vector<int> permute(int n, long long k) {
        F[0]=1ll; for (lld i=1; i<20; i++) { F[i]=F[i-1]*i; }
        memset(U,false,sizeof(U)); int pp=-1;
        vector<int> ans={};
        for (int i=0; i<n; i++) {
            vector<int> curval={};
            if (!i) { if ((n&1)==1) {pp=0;} }
            int ppForInit = pp;
            if (ppForInit!=-1) {ppForInit=!(ppForInit);}
            initCurval(curval,ppForInit,n);
            vector<int> candidates={};
            int totval=curval.size();
            if (ppForInit!=-1) {VC[ppForInit]--;}
            else {VC[0]--;}
            candidates={VC[0],VC[1]};
            int assignedVal=-1;
            if (isOverflow(candidates,k)) {
                assignedVal=curval[0];}
            else {
                lld pat=1ll; lld ra,rb; ra=1ll; rb=0ll;
                for (int c: candidates) {pat*=F[c];}
                for (int i=0; i<totval&&assignedVal==-1; i++) {
                    rb+=pat;
                    if (ra<=k&&rb>=k) {
                        assignedVal=curval[i];
                        k=k-ra+1ll;
                        break;
                    }
                    ra=rb+1ll;
                }
            }
            if (assignedVal==-1) {return {};}
            U[assignedVal]=true;
            ans.push_back(assignedVal);
            pp=(assignedVal&1);
        }
        return ans;
    }
};
```
['C++']