Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

• 1 is a super ugly number for any given primes.
• The given numbers in primes are in ascending order.
• 0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000

Example:

Given n = 6, primes = [2, 7, 13, 19] return 13.

Solution:

Version 1: extension to Ugly Number II. Instead of using p2, p3, and p5, we use a pointer array. Better Solution

Version 2: similar to Kth Smallest Number in Sorted Matrix.

• Step 1, create a PriorityQueue and a HashSet to store the found ugly numbers
• Step 2, initialize them with 1 and all given primes. (primes[i] * 1 = primes[i])
• Step 3, according to the definition of super ugly number (a positive numbers whose all prime factors are in the given list), we could have:
  • the next minimal ugly number is in the list of ( current minimal ugly number * each previously found guly number)

Code:

//version 1
public class Solution {

    public int nthSuperUglyNumber(int n, int[] primes) {
        if (primes == null || primes.length == 0) {
            return Integer.MIN_VALUE;
        }
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < idx.length; j++) {
                min = Math.min(min, primes[j] * ugly[idx[j]]);
            }
            ugly[i] = min;
            for (int j = 0; j < idx.length; j++) {
                while (ugly[idx[j]] * primes[j] <= ugly[i]) {
                    idx[j]++;
                }
            }
        }
        return ugly[n - 1];
    }
}

//version 2
public class Solution {

    public int nthSuperUglyNumber(int k, int[] primes) {
        if (primes == null || primes.length == 0) {
            return Integer.MIN_VALUE;
        }
        int n = primes.length;
        Queue<Integer> q = new PriorityQueue<>(k * k + n);
        HashSet<Integer> visited = new HashSet<>();
        addHelper(1, 1, q, visited);
        for (int i = 0; i < n; i++) {
            addHelper(1, primes[i], q, visited);
        }
        List<Integer> list = new ArrayList<>();
        while (list.size() < k) {
            int min = q.poll();
            list.add(min);
            //add the product of current min with each other ugly number to the queue
            for (int x : list) {
                addHelper(x, min, q, visited);
            }
        }
        return list.get(list.size() - 1);
    }

    private void addHelper(int a, int b, Queue<Integer> q, 
                    HashSet<Integer> visited) {
        //double is used to avoid overflow
        double t = a;
        t = t * b;
        if (t >= Integer.MAX_VALUE) {
            return;
        }
        int p = a * b; 
        if (p < Integer.MAX_VALUE && !visited.contains(p)) {
            q.offer(p);
            visited.add(p);
        }
    }
}