C# Solution for Ugly Number II Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem of finding the nth ugly number can be approached using a min-heap (priority
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem of finding the nth ugly number can be approached using a min-heap (priority queue) to ensure that we always process the smallest possible ugly number at each step. By maintaining a heap of generated ugly numbers and continuously extracting the smallest, we can build the sequence of ugly numbers efficiently. This method allows us to avoid generating non-ugly numbers and ensures the sequence is generated in sorted order.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tMin-Heap (Priority Queue):\n\t\u2022\tInitialize a min-heap with the first ugly number, which is 1.\n\t\u2022\tUse a HashSet to keep track of numbers already added to the heap to prevent duplicates.\n2.\tGenerate Ugly Numbers:\n\t\u2022\tRepeatedly extract the smallest number from the heap (this is the next ugly number in the sequence).\n\t\u2022\tMultiply the extracted number by 2, 3, and 5 to generate new potential ugly numbers.\n\t\u2022\tAdd these new numbers to the heap, but only if they haven\u2019t been added before (using the HashSet to check).\n3.\tContinue Until nth Ugly Number:\n\t\u2022\tRepeat the extraction and multiplication process until the nth ugly number is extracted from the heap.\n4.\tReturn the nth Ugly Number:\n\t\u2022\tAfter n iterations, the value extracted from the heap is the nth ugly number.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tHeap Operations: Inserting and extracting elements from a min-heap (priority queue) each take O(log k) time, where k is the current size of the heap.\n\u2022\tTotal Complexity: Since we perform n extractions and may insert up to 3n elements into the heap, the overall time complexity is O(n log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tHeap and HashSet: The space complexity is O(n), as the heap and hash set will store all distinct ugly numbers generated up to the nth one. In the worst case, this involves keeping up to 3n elements in the heap and hash set, but usually, the actual size will be around n due to overlaps and duplications in multiples.\n\n# Code\n```\npublic class Solution {\n    public int NthUglyNumber(int n) {\n        HashSet<long> seen = new HashSet<long>();\n        PriorityQueue<long, long> heap = new PriorityQueue<long, long>();\n        \n        // Initial ugly number is 1\n        heap.Enqueue(1, 1);\n        seen.Add(1);\n        \n        long[] primes = { 2, 3, 5 };\n        long ugly = 1;\n        \n        for (int i = 0; i < n; i++) {\n            // Extract the smallest ugly number\n            ugly = heap.Dequeue();\n            \n            // Generate new ugly numbers and add them to the heap\n            foreach (long prime in primes) {\n                long newUgly = ugly * prime;\n                if (!seen.Contains(newUgly)) {\n                    seen.Add(newUgly);\n                    heap.Enqueue(newUgly, newUgly);\n                }\n            }\n        }\n        \n        return (int)ugly;\n    }\n}\n```
['C#']