# 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`.

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.

## 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];
}
}
``````