← Back to Index

📚 Super Ugly Number – Java Cheat Sheet

📌 What Is It?

The problem involves finding the n-th super ugly number. A super ugly number is a positive integer whose prime factors are in a given list of primes.

This problem can be efficiently solved using a min-heap to track the smallest multiples of the primes.

🧱 Pattern Template

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        ugly[0] = 1;

        // Each entry: [nextVal, prime, index_in_ugly_array]
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        for (int prime : primes) {
            pq.offer(new long[]{prime, prime, 0});
        }

        for (int i = 1; i < n; ) {
            long[] top = pq.poll();
            long nextVal = top[0];
            long prime = top[1];
            int idx = (int) top[2];

            if (nextVal != ugly[i - 1]) {
                ugly[i++] = (int) nextVal;
            }

            long newVal = prime * ugly[idx + 1];
            pq.offer(new long[]{newVal, prime, idx + 1});
        }

        return ugly[n - 1];
    }
}

📊 Time Complexity

• Heap Initialization: O(k log k) – Adding the first multiples of each prime to the heap, where k is the number of primes.
• Heap Operations: O(n log k) – Extracting and adding elements to the heap for n iterations.
• Overall Complexity: O(n log k).

✅ Use Cases

• Finding the n-th smallest number with specific prime factors
• Efficiently generating sequences of numbers with constraints
• Applications in optimization and scheduling problems

📘 Common LeetCode Problems

• 313. Super Ugly Number [Medium] Heap

🧪 Example: Super Ugly Number

Input: n = 12, primes = [2,7,13,19]
Output: 32

Explanation:
- The sequence of super ugly numbers is [1, 2, 7, 13, 14, 19, 26, 28, 32, ...].
- The 12th super ugly number is 32.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest multiples of the primes.
• Edge cases: n = 1, primes with duplicates.
• Ensure the heap stores enough information to track the prime and its current multiple.