Intuitive Solution, Similar to find rank of word in dictionary, C++
This question is similar to finding rank of a given word in dictionary which is constituted by "H" and "V" characters only. \nFirst thing we need to know is the
This question is similar to finding rank of a given word in dictionary which is constituted by "H" and "V" characters only. \nFirst thing we need to know is the number of steps needed to reach the destination. Suppose destination is (x, y) and we know that starting point is (0, 0), then the number of steps would be:\n```\ndistance = (x-0) + (y-0) = x+y\n```\n\nSo the string\'s length would be of length ```x+y```. \n\nOne more thing to observe is that this string will be made up of **x** V\'s and **y** H\'s. This is because we whichever path we take we will have to move x steps downwards and y steps rightwards. So the final string will be a permutation of the string\n```\n"HHHH....(y-times)VVVVVV.....(x-times)"\n```\n\n**Combination**\nThe number of strings with x V\'s and y H\'s can be written as:\nN = (h + v)! / ( h! * v! )\n\nThis is equivalent to : ``` (h+v)C(h) or  (h+v)C(v)``` \n\nThus the required string can be formed by finding the ```kth``` permutation of this string. \nSteps to find the ```kth``` string:\n```\nlet v = number of vertical steps\n\th = number of horizontal steps\n\tans = reuired string\n\tcomb = number permutations of string having h - H\'s and v - V\'s\n\tcurr = rank of current string\n\tk = rank of the required string\n1. Take an empty string, suppose ans = ""\n2. Since the smallest string of length h+v will start with "H", \n\t\t1. \tIf h!=0, then we find number of string starting with H as \n\t\t\t\t\t\t\tcomb = "H" + Combination( (h-1) + v, h-1)\n\t\t\t\t\t\t\th--;\n\t\t2. Else, no H is left so we add "V" at the end\n\t\t\t\t\t\t\tans = ans + "V"\n\t\t\t\t\t\t\tv--\n3. Check if the curr+comb<=k, if yes then replace "H" with "V" and curr = curr+comb. This indicates that the required string has rank greater than the rank of largest rank string with "H" at the current index.\n4. If ans.length< required string\'s length, go back to step 2\n5. Else the ans is the required string.\n```\n\n**Note**\n* I have implemented the function `Combination (int n, int r) ` separately in order to calculate nCr without overflow\n* **curr** starts with 1 because rank is 1-indexed and the first string generated would be at rank 1 and not rank 0. e.g: "HHVV" will be at rank 1, but if curr starts with 0 the answers comes out to be 0 as there are no other strings before 1.\nCode:\n\n```\n#define ll long long\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        int n = destination[0]+destination[1];\n        int curr=1, v=destination[0], h=destination[1];\n        string ans="";\n        for(int i=0; i<n; i++){\n            if(h>0){\n                ans += "H";\n                h--;\n            }\n            else{\n                ans += "V";\n                v--;\n            }\n            ll comb = combination(h+v, h);\n            if(curr+comb<=k){\n                curr += comb;\n                ans[ans.size()-1] = \'V\';\n                h++;\n                v--;\n            }\n        }\n        return ans;\n    }\n    \n    ll combination(int n, int r){\n        ll ans = 1, k=1;\n        if (n - r < r) \n            r = n - r; \n\n        if (r != 0) { \n            while (r) { \n                ans *= n; \n                k *= r; \n                long long m = __gcd(ans, k);\n                ans /= m; \n                k /= m; \n\n                n--; \n                r--; \n            }  \n        } \n        else\n            ans = 1;\n        return ans;\n    }\n};\n```\n\n\n**Time Complexity:** `O((r+c)*r*log(r))`\n**Explaination:** `r+c - is constituted by the first for loop, r - constituted by while loop if function combination(), log(r) - is constituted by the __gcd() function`\n\n**Space Complexity:** `O(r+c), taken by the answer string`
['Math', 'C', 'Combinatorics']