Skip to content

313 Super Ugly Number

Problem:

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.

Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000. (4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Solutions:

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] result = new int[n];
        result[0] = 1;
        int[] next = new int[primes.length];
        for (int i = 1; i < n; i ++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j ++) {
                min = Math.min(min, primes[j] * result[next[j]]);
            }
            for (int j = 0; j < primes.length; j ++) {
                if (primes[j] * result[next[j]] == min){
                    next[j] ++;
                }
            }
            result[i] = min;
        }
        return result [n - 1];
    }
}

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] result = new int[n];
        result[0] = 1;
        int[] next = new int[primes.length];

        HashMap<Integer, List<Integer>> index = new HashMap<Integer, List<Integer>>();
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        for (int i = 0; i < primes.length; i ++) {
            q.add(primes[i]);
            index.put(primes[i], new LinkedList<Integer>());
            index.get(primes[i]).add(i);
        }

        for (int i = 1; i < n; i ++) {
            int min = q.poll();
            List<Integer> indexToUpdate = index.get(min);
            result[i] = min;
            for (Integer j:indexToUpdate) {
                next[j] ++;
                int cand = result[next[j]] * primes[j];
                if (index.containsKey(cand)) {
                    index.get(cand).add(j);
                }
                else {
                    index.put(cand, new LinkedList<Integer>());
                    index.get(cand).add(j);
                    q.add(cand);
                }
            }
        }


        return result [n - 1];
    }
}