C++ | Simple and detailed explanation
We have to find the nth ugly number.\n\nWe can check for all numbers up to n whether it is ugly or not and return the nth ugly number. But that would lead to a 
We have to find the nth ugly number.\n\nWe can check for all numbers up to `n` whether it is ugly or not and return the nth ugly number. But that would lead to a TLE for numbers like `1690`.\n\nBetter approach is to check only for the multiples of `2`, `3`, or `5`, and return the nth ugly number. \n\nHere, we store all the ugly numbers till n by maintaining a track of the indices of the multiples of 2, 3 and 5. We do this for creating a sorted list of all the ugly numbers. We return the last number in the list. Code for this approach is  shown below. \n\nPlease post your comments/queries in the comments section.\n\n```\nclass Solution {\nprivate:\n    \npublic:\n    int nthUglyNumber(int n) {\n        if(n == 1)\n            return 1;\n        vector<int> uglies(n);\n        uglies[0] = 1;\n        int l2 = 0, l3 = 0, l5 = 0; //indexes for respective list\n        for(int i=1; i<n; i++)\n        {\n            uglies[i] = min(2 * uglies[l2], min(3 * uglies[l3], 5 * uglies[l5]));\n            if(uglies[i] == 2 * uglies[l2])\n                l2++;\n            if(uglies[i] == 3 * uglies[l3])\n                l3++;\n            if(uglies[i] == 5 * uglies[l5])\n                l5++;\n        }\n        return uglies[n - 1];\n    }\n};\n```\n\nIf you liked my explanation, then would you be so kind as to upvote my post? It gives me motivation to keep explaining questions in a simple and detailed manner.
['Dynamic Programming']