C++ O(n) explained
Fundamentals\n\n- We need to move to the right col steps and down row steps to reach to the destination (bottom right) cell => the result string is always:\n  -
#### Fundamentals\n\n- We need to move to the right `col` steps and down `row` steps to reach to the destination (bottom right) cell => the result string is always:\n  - of length `col + row`\n  - consisted of `row` \'H\'s and `col` \'V\'s\n- The possible strings are **lexicographically ordered** => \'H\' < \'V\'\n- The total number of possible paths (number of combinations of `row` \'H\'s and `col` \'V\'s) is `nCr(row + col, row)`. i.e., `"length of string" choose "number of H"`\n  - Why? We have `row + col` positions in the string, we need to choose `row` of them for \'H\'.\n- How to calculate `N choose K`?\n  - `N!/(N-K)!/K!` (Why? this is a math question. I\'m not going to explain it here)\n  - `tgamma(x)` returns `(x-1)!`\n  - There are many other methods to calculate `N choose K`\n\n#### Solve the Problem\n\n1. Let\'s only consider the first letter.\n  a) Say, we have `h` of \'H\'s and `v` of \'V\'s, there are `x` possible combinations (`x = nCr(h+v, h)`)\n  b) The chance we choose \'H\' for the first letter is `h/(h+v)` => in all combinations, there are `y` of them (`y = x * h/(h+v)`) have \'H\' as the first letter\n  c) All the combinations are *lexicographically ordered* => the **first** `y` combinations have \'H\' as the first letter\n  d) We want the *kth* combination => **if `k <= y`, the first letter should be \'H\', otherwise it should be \'V\'.**\n2. We have found the first letter. Now let\'s look at the next one:\n\ta) If the first letter is \'H\'\n\t\t- The number of combinations start with \'H\' is `y` (calculated in step 1)\n\t\t- We have used one \'H\', and we have `h-1` left\n\t\t- The length of rest of strting is `h+v-1`\n\t\t- The remaining combinations (all start with \'H\') - from 1st to yth, since k fell into this range, it remains the same (we need to find kth combination of 1 to y).\n\tb) If the first letter is \'V\'\n\t\t- The number of combinations start with \'V\' is `x - y`\n\t\t- We didn\'t use \'H\', so we still have `h` \'H\'s left\n\t\t- The length of rest of strting is `h+v-1`\n\t\t- The remaining combinations (all start with \'V\') are from `y+1` to `x` => we need to find (kth from 1st, that is) `k-y`th combination from `y+1`.\n\tc) Apply same method of step 1, we can find the 2nd letter.\n3. Repeated step 2 until we used either all \'H\'s or all \'V\'s.\n4. Fill rest of the string with the other letter.\n\n#### Code\n\n```cpp\nclass Solution {\npublic:\n    size_t NChooseK(int n, int k) {\n        return round(tgamma(n+1)/tgamma(k+1)/tgamma(n-k+1));\n    }\n    \n    string kthSmallestPath(vector<int>& destination, int k) {\n        int numHLeft = destination[1], numCharsToBuild = destination[0] + destination[1];\n        uint64_t totalMax = NChooseK(numCharsToBuild, numHLeft);\n        string ans = "";\n        while (numHLeft && numHLeft < numCharsToBuild) {\n            uint64_t maxH = totalMax*numHLeft/numCharsToBuild;\n            if (k <= maxH) {\n                ans += "H";\n                numHLeft--;\n                totalMax = maxH;\n            } else {\n                ans += "V";\n                totalMax -= maxH;\n\t\t\t\tk -= maxH;\n            }\n            numCharsToBuild--;\n        }\n        ans += string(numCharsToBuild, numHLeft ? \'H\' : \'V\');\n        return ans;\n    }\n};\n```\n\n#### Complexity\n\nWe built the string of length `row + col` letter by letter => O(n), where `n = row + col`\n\n#### Additional Note\n\nCalculating `N choose K` can be time consuming. We only need to calculate it **once** in this solution, instead of _every step_ (like many other solutions do).\n
['C']