No DP || Easy Min-Heap || Beginner friendly || 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nConverted the DFS of multipying 1 with 2,3 and 5 and then again with the same.\n\n# App
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nConverted the DFS of multipying 1 with 2,3 and 5 and then again with the same.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe start with 1 and then keep multiplying the numbers with `2, 3 and 5` \n```\n1\n\u251C\u2500\u2500 2\n\u2502   \u251C\u2500\u2500 4\n\u2502   \u2502   \u251C\u2500\u2500 8\n\u2502   \u2502   \u251C\u2500\u2500 12\n\u2502   \u2502   \u2514\u2500\u2500 20\n\u2502   \u251C\u2500\u2500 6\n\u2502   \u2502   \u251C\u2500\u2500 12\n\u2502   \u2502   \u251C\u2500\u2500 18\n\u2502   \u2502   \u2514\u2500\u2500 30\n\u2502   \u2514\u2500\u2500 10\n\u2502       \u251C\u2500\u2500 20\n\u2502       \u251C\u2500\u2500 30\n\u2502       \u2514\u2500\u2500 50\n\u251C\u2500\u2500 3\n\u2502   \u251C\u2500\u2500 6\n\u2502   \u2502   \u251C\u2500\u2500 12\n\u2502   \u2502   \u251C\u2500\u2500 18\n\u2502   \u2502   \u2514\u2500\u2500 30\n\u2502   \u251C\u2500\u2500 9\n\u2502   \u2502   \u251C\u2500\u2500 18\n\u2502   \u2502   \u251C\u2500\u2500 27\n\u2502   \u2502   \u2514\u2500\u2500 45\n\u2502   \u2514\u2500\u2500 15\n\u2502       \u251C\u2500\u2500 30\n\u2502       \u251C\u2500\u2500 45\n\u2502       \u2514\u2500\u2500 75\n\u2514\u2500\u2500 5\n    \u251C\u2500\u2500 10\n    \u2502   \u251C\u2500\u2500 20\n    \u2502   \u251C\u2500\u2500 30\n    \u2502   \u2514\u2500\u2500 50\n    \u251C\u2500\u2500 15\n    \u2502   \u251C\u2500\u2500 30\n    \u2502   \u251C\u2500\u2500 45\n    \u2502   \u2514\u2500\u2500 75\n    \u2514\u2500\u2500 25\n        \u251C\u2500\u2500 50\n        \u251C\u2500\u2500 75\n        \u2514\u2500\u2500 125\n\n```\nand for every iteration pick up the `smallest element`.\n\nBut, how do we get the smallest element, in every iteration,\nIs there any Data Structure which always gives the smallest element.\n\nOhh yes there is and its called `Min-Heap`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g.  -->\n$$O(n * logn)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass Solution\n{\npublic:\n    typedef long long ll;\n\n    int nthUglyNumber(int n)\n    {\n        // Create a min Heap\n        priority_queue<ll, vector<ll>, greater<ll>> pq;\n        // Set to check so that we do not add the same number twice\n        unordered_set<ll> vis;\n\n        pq.push(1);\n        vis.insert(1);\n\n        ll val = 1;\n\n        while (n > 0)\n        {\n            //Take the top element\n            val = pq.top();\n            pq.pop();\n            n--; \n\n            if (vis.find(val * 2) == vis.end())\n            {\n                pq.push(val * 2);\n                vis.insert(val * 2);\n            }\n            if (vis.find(val * 3) == vis.end())\n            {\n                pq.push(val * 3);\n                vis.insert(val * 3);\n            }\n            if (vis.find(val * 5) == vis.end())\n            {\n                pq.push(val * 5);\n                vis.insert(val * 5);\n            }\n        }\n\n        return val; // After n iterations this is the number you get\n    }\n};\n```
['Hash Table', 'Heap (Priority Queue)', 'Ordered Set', 'C++']