0ms solution. Beats 100% (detailed explanation)
\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        int dp[n];\n        int i2=0;int i3=0;int i5=0;\n        dp[0]=1;\n        for(int i=1;i<n;
```\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        int dp[n];\n        int i2=0;int i3=0;int i5=0;\n        dp[0]=1;\n        for(int i=1;i<n;i++)\n        {\n            int least= min(min(dp[i2]*2,dp[i3]*3),dp[i5]*5);  \n            if(least == dp[i2]*2)\n                i2++;\n            if(least == dp[i3]*3)\n                i3++;\n            if(least == dp[i5]*5)\n                i5++;\n            dp[i]=least;\n        }\n        return dp[n-1];\n    }\n};\n```\nThe idea is that every ugly number can be formed from some smaller ugly number by multiplying 2,3 or 5. We will use 3 pointers(i2,i3,i5) and a dynamic programming logic to use previously calculated uglyNumbers to find the next one.\nuglyNumber[n] = min({uglyNumber[i2] * 2 , uglyNumber[i3] * 3, uglyNumber[i5]* 5}) where\nik represents the index of the previously calculated uglyNumber which we need to check next by multiplying with k; where k is 2,3 or 5;\nExample, \ndp array represents all uglyNumbers and the value of uglyNumber at i should be the minimum amongst the ones we haven\'t considered yet.\ninitially, i2=0;i3=0;i5=0;\ndp[0]=1 as 1 is the first uglyNumber. .\ndp[1] = min(dp[0] * 2, dp[0] * 3, dp[0] * 5) = min(2,3,5) = 2 hence i2 will increase by 1; (as value corresponding to i2 is the minimum and we have considered dp[0]* 2 so the next multiple of 2 we need to consider would be that of the next uglyNumber which is stored in dp[1] now )\ndp[2] = min(dp[1] * 2, dp[0] * 3, dp[0] * 5) = min(4,3,5) = 3 hence i3 will increase by 1 i2=1;i3=1;i5=0\ndp[3] = min(dp[1] * 2, dp[1] * 3, dp[0] * 5) = min(4,6,5) = 4 hence i2 will increase by 1 i2=2;i3=1;i5=0\ndp[4] = min(dp[2] * 2, dp[1] * 3, dp[0] * 5) = min(6,6,5) = 5 hence i5 will increase by 1 i2=2;i3=1;i5=1\ndp[5] = min(dp[2] * 3, dp[1] * 3, dp[1]* 5) = min(6,6,10) = 6 hence both i2 and i3 will increase by 1 i2=3;i3=2;i5=1;\nand so on...\ndp[n-1] would give us the nth uglyNumber.\n\n\n
['Dynamic Programming']