Super Ugly Number

Write a program to find thenthsuper ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime listprimesof sizek.

Example:

Input:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [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 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.

• The n th super ugly number is guaranteed to fit in a 32-bit signed integer.

Analysis

Very similar to Ugly Number II problem.

See reference: https://leetcode.com/problems/super-ugly-number/discuss/76291/Java-three-methods-23ms-36-ms-58ms(with-heap)-performance-explained

Solution

Heap - (193 ms AC 13.61%)

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.offer(1);
        for (int prime : primes) {
            pq.offer(prime);
        }
        for (int i = 1; i < n; i++) {
            int tmp = pq.poll();
            while (!pq.isEmpty() && pq.peek() == tmp) {
                tmp = pq.poll();
            }
            for (int prime : primes) {
                long multiply = (long) tmp * (long) prime;
                if (multiply < Integer.MAX_VALUE) {
                    pq.offer((int) multiply); 
                }
            }
        }
        return pq.poll().intValue();
    }
}

DP (9ms 100% AC)

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

DP 2

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