Simple C++ Solution using min-heap
The main problem is how to maintain the order of the generated ugly numbers, ie, how can we get {1,2,3,4,5,...} instead of {1,2,4,3,6,5...} which is a general r
The main problem is how to maintain the order of the generated ugly numbers, ie, how can we get {1,2,3,4,5,...} instead of {1,2,4,3,6,5...} which is a general result of generating the ugly numbers using pow method while maintaining three pointers for 2,3,5 respectively.\n\nWe can maintain a min heap and keep inserting the numbers obtained by multiplying a given number with 2,3 and 5 respectively. Initialise the min heap with 1. Now observe the following example:\n- pop 1 from queue\n- check if we have encountered this number before\n- insert 1* 2, 1* 3, 1* 5 into the queue which will automatically maintain the order and during the next pop operation, provide us with the next smallest ugly number.\n- increase the count as we just popped an ugly number from the prior queue.\n- continue the same till count becomes n.\n- return the last popped element as it was the one who set the count to n and hence is the nth ugly number.\n\n```\nint nthUglyNumber(int n) {\n        //a hash map to see if a certain number was already popped; for ex: 2*3 and 3*2\n        //will both add 6 to the pq, but we will only have to count it once.\n        unordered_map<long long, int> map;\n        priority_queue<long long, vector<long long>, greater<long long>> pq;\n        \n        pq.push(1);\n        int count= 0;\n        long long popped;\n        \n        while(count<n){\n            popped= pq.top();\n            pq.pop();\n            if(map[popped]== 0){\n                pq.push(popped*2);\n                pq.push(popped*3);\n                pq.push(popped*5);\n                count++;\n                map[popped]= 1;\n            }\n        }\n        return int(popped);\n\t}
['Heap (Priority Queue)', 'C++']