Super Ugly Number
Problem
Find the nth super ugly number whose only prime factors come from a list of primes.
n = 12, primes = [2,7,13,19]32def nth_super_ugly_number(n, primes):
ugly = [1]
ptr = [0] * len(primes)
while len(ugly) < n:
cands = [primes[i] * ugly[ptr[i]] for i in range(len(primes))]
nxt = min(cands)
ugly.append(nxt)
for i in range(len(primes)):
if cands[i] == nxt: ptr[i] += 1
return ugly[-1]function nthSuperUglyNumber(n, primes) {
const ugly = [1];
const ptr = primes.map(() => 0);
while (ugly.length < n) {
const cands = primes.map((p, i) => p * ugly[ptr[i]]);
const next = Math.min(...cands);
ugly.push(next);
for (let i = 0; i < primes.length; i++) if (cands[i] === next) ptr[i]++;
}
return ugly[n - 1];
}class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n]; ugly[0] = 1;
int[] ptr = new int[primes.length];
for (int k = 1; k < n; k++) {
int next = Integer.MAX_VALUE;
for (int i = 0; i < primes.length; i++) next = Math.min(next, primes[i] * ugly[ptr[i]]);
ugly[k] = next;
for (int i = 0; i < primes.length; i++) if (primes[i] * ugly[ptr[i]] == next) ptr[i]++;
}
return ugly[n - 1];
}
}int nthSuperUglyNumber(int n, vector& primes) {
vector ugly(n, 0); ugly[0] = 1;
vector ptr(primes.size(), 0);
for (int k = 1; k < n; k++) {
int next = INT_MAX;
for (int i = 0; i < (int)primes.size(); i++) next = min(next, primes[i] * ugly[ptr[i]]);
ugly[k] = next;
for (int i = 0; i < (int)primes.size(); i++) if (primes[i] * ugly[ptr[i]] == next) ptr[i]++;
}
return ugly[n - 1];
} Explanation
We build the sequence of ugly numbers in order, one at a time. The key idea is that every new ugly number is some earlier ugly number multiplied by one of the given primes, so we keep a pointer per prime that walks along the sequence we are building.
We start the list ugly with 1. Each prime i has a pointer ptr[i] into ugly, so its current candidate is primes[i] * ugly[ptr[i]].
Each round we compute every prime's candidate, take the smallest one as the next ugly number, and append it. Then we advance the pointer of every prime that produced that same minimum (there can be ties), which avoids adding duplicates.
Example: primes = [2, 7, 13, 19]. Starting from ugly = [1], candidates are 2, 7, 13, 19, so 2 is next. Now 2's pointer advances, giving candidates 4, 7, 13, 19, so 4 is next, and so on, producing 1, 2, 4, 7, 8, 13, ....
We repeat until the list has n numbers and return the last one. Always picking the smallest candidate guarantees the sequence comes out sorted with no gaps.