Min Heap ||  with Dry Run
\n# Code\n\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        # take a min heap and insert 1 into it as \n        #there is no prime factor 
\n# Code\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        # take a min heap and insert 1 into it as \n        #there is no prime factor for 1\n        min_heap = [1] \n        #take one variable which records no of variable which have been\n        # recorded already\n        seen = set([1]) \n        prime_no = (2,3,5)\n        #iterating n-1 times\n        for i in range(n-1):  \n            ugly_no = heapq.heappop(min_heap)\n            for ele in prime_no:\n                no = ugly_no * ele\n                if no not in seen:\n                    seen.add(no)\n                    heapq.heappush(min_heap, no)\n        return min_heap[0]\n\n```\n\n# DRY RUN\n------iteration----no-------  0\nugly 1\nproduct 2\nseen [1, 2]\nminHeap [2]\nproduct 3\nseen [1, 2, 3]\nminHeap [2, 3]\nproduct 5\nseen [1, 2, 3, 5]\nminHeap [2, 3, 5]\n------iteration----no-------  1\nugly 2\nproduct 4\nseen [1, 2, 3, 5, 4]\nminHeap [3, 5, 4]\nproduct 6\nseen [1, 2, 3, 5, 4, 6]\nminHeap [3, 5, 4, 6]\nproduct 10\nseen [1, 2, 3, 5, 4, 6, 10]\nminHeap [3, 5, 4, 6, 10]\n------iteration----no-------  2\nugly 3\nproduct 6\nproduct 9\nseen [1, 2, 3, 5, 4, 6, 10, 9]\nminHeap [4, 5, 10, 6, 9]\nproduct 15\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15]\nminHeap [4, 5, 10, 6, 9, 15]\n------iteration----no-------  3\nugly 4\nproduct 8\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8]\nminHeap [5, 6, 8, 15, 9, 10]\nproduct 12\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12]\nminHeap [5, 6, 8, 15, 9, 10, 12]\nproduct 20\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20]\nminHeap [5, 6, 8, 15, 9, 10, 12, 20]\n------iteration----no-------  4\nugly 5\nproduct 10\nproduct 15\nproduct 25\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25]\nminHeap [6, 9, 8, 15, 20, 10, 12, 25]\n------iteration----no-------  5\nugly 6\nproduct 12\nproduct 18\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18]\nminHeap [8, 9, 10, 15, 20, 25, 12, 18]\nproduct 30\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30]\nminHeap [8, 9, 10, 15, 20, 25, 12, 18, 30]\n------iteration----no-------  6\nugly 8\nproduct 16\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16]\nminHeap [9, 15, 10, 16, 20, 25, 12, 30, 18]\nproduct 24\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24]\nminHeap [9, 15, 10, 16, 20, 25, 12, 30, 18, 24]\nproduct 40\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24, 40]\nminHeap [9, 15, 10, 16, 20, 25, 12, 30, 18, 24, 40]\n------iteration----no-------  7\nugly 9\nproduct 18\nproduct 27\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24, 40, 27]\nminHeap [10, 15, 12, 16, 20, 25, 40, 30, 18, 24, 27]\nproduct 45\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24, 40, 27, 45]\nminHeap [10, 15, 12, 16, 20, 25, 40, 30, 18, 24, 27, 45]\n------iteration----no-------  8\nugly 10\nproduct 20\nproduct 30\nproduct 50\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24, 40, 27, 45, 50]\nminHeap [12, 15, 25, 16, 20, 45, 40, 30, 18, 24, 27, 50]\n\n---------------------HERE IS THE FINAL OUTPUT-------------------------\noutput 12\nseen [1, 2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 16, 24, 40, 27, 45, 50]\nminheap [12, 15, 25, 16, 20, 45, 40, 30, 18, 24, 27, 50]
['Python3']