DCC - 18 AUGUST 2024 || PRIORITY-QUEUE || N*LOGN 🔥
Approach and Intuition\n\nThe problem is to find the \(n\)th ugly number. An ugly number is defined as a number whose only prime factors are 2, 3, or 5. The seq
### Approach and Intuition\n\nThe problem is to find the \\(n\\)th ugly number. An ugly number is defined as a number whose only prime factors are 2, 3, or 5. The sequence of ugly numbers starts with 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and so on.\n\n#### Steps:\n\n1. **Initialization**: \n   - Use a `PriorityQueue` (min-heap) to efficiently retrieve the smallest ugly number.\n   - Use a `HashSet` to avoid inserting duplicate numbers into the priority queue.\n\n2. **Generating Ugly Numbers**:\n   - Start with the smallest ugly number, which is 1, and insert it into the priority queue.\n   - Repeatedly extract the smallest element from the priority queue and generate new ugly numbers by multiplying it with the factors 2, 3, and 5.\n   - If the product is not already in the set, insert it into both the set and the priority queue.\n   - Continue this process until the \\(n\\)th ugly number is extracted from the priority queue.\n\n3. **Returning the Result**:\n   - The loop will run exactly \\(n\\) times, and after the \\(n\\)th iteration, the smallest element in the priority queue is the \\(n\\)th ugly number.\n\n### Complexity Analysis\n\n- **Time Complexity**:\n  - Inserting and removing elements from the priority queue (min-heap) takes \\(O(log k)\\) time, where \\(k\\) is the number of elements in the heap. In this case, the heap size grows as more ugly numbers are generated.\n  - Each iteration involves generating three new numbers (by multiplying with 2, 3, and 5), checking if they exist in the set, and then inserting them if not already present.\n  - Thus, the overall time complexity is approximately \\(O(n*log k)\\), where \\(k\\) is bounded by the size of the heap. In practice, \\(k\\) is proportional to \\(n\\).\n\n- **Space Complexity**:\n  - The space complexity is \\(O(n)\\) for storing the \\(n\\) ugly numbers in the priority queue and the set. Each ugly number is processed only once, and there are at most \\(3n\\) operations involving insertion into the set and priority queue.\n\n\n# Code\n```\nclass Solution {\n    public int nthUglyNumber(int n) {\n       int[] factor = {2,3,5};\n       PriorityQueue<Long> q = new PriorityQueue<>();\n       HashSet<Long> set = new HashSet<>();\n       q.offer(1L);\n       set.add(1L);\n       long temp=0;\n       for(int i=1;i<=n;i++){\n        temp = q.poll();\n        for(int j:factor){\n            if(!set.contains(temp*j))\n            q.offer(temp*j);\n            set.add(temp*j);\n        }\n       }\n       return (int)temp;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']