simple efficient solution
\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int>dp={1};\n        int two=0,three=0,five=0;\n        for(int i=0;i<n-1;++i){\n   
```\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int>dp={1};\n        int two=0,three=0,five=0;\n        for(int i=0;i<n-1;++i){\n          int tmp=min(min(2*dp[two],3*dp[three]),5*dp[five]);\n          dp.push_back(tmp);\n          if(tmp==dp[two]*2)\n            ++two;\n          if(tmp==dp[three]*3)\n            ++three;\n          if(tmp==dp[five]*5)\n            ++five;\n        }\n        cout<<dp.size();\n        for(int i:dp)\n          cout<<\' \'<<i;\n        return dp.back();\n    }\n};\n```
['Dynamic Programming', 'C']