Super Ugly Number

Problem

Super ugly numbers only have prime factors from a given primes array. Find the nth one.

Key insight: Generalize ugly number II. K pointers (one per prime), each pointing to the next ugly to multiply by that prime.

Solutions

// C++
int nthSuperUglyNumber(int n, vector<int>& primes) {
    int k = primes.size();
    vector<int> ugly(n), idx(k, 0);
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        int mn = INT_MAX;
        for (int j = 0; j < k; j++) mn = min(mn, ugly[idx[j]] * primes[j]);
        ugly[i] = mn;
        for (int j = 0; j < k; j++) if (ugly[idx[j]] * primes[j] == mn) idx[j]++;
    }
    return ugly[n-1];
}

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

// JavaScript
function nthSuperUglyNumber(n, primes) {
    const ugly = [1], idx = new Array(primes.length).fill(0);
    for (let i = 1; i < n; i++) {
        const next = Math.min(...primes.map((p, j) => ugly[idx[j]] * p));
        ugly.push(next);
        primes.forEach((p, j) => { if (ugly[idx[j]] * p === next) idx[j]++; });
    }
    return ugly[n-1];
}

# Python
def nthSuperUglyNumber(n, primes):
    ugly = [1]
    idx = [0] * len(primes)
    for _ in range(n - 1):
        next_val = min(ugly[idx[j]] * p for j, p in enumerate(primes))
        ugly.append(next_val)
        for j, p in enumerate(primes):
            if ugly[idx[j]] * p == next_val:
                idx[j] += 1
    return ugly[-1]

Complexity

Time: O(n * k) — k pointers per step
Space: O(n + k)

Key Insight

Same as Ugly Number II but generalized to k primes. Increment ALL pointers whose product equals the current minimum to avoid duplicates.