Code Implementation

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        ugly = [1]
        idx = [0] * len(primes)
        values = list(primes)
        for i in range(1, n):
            next_ugly = min(values)
            ugly.append(next_ugly)
            for j in range(len(primes)):
                if values[j] == next_ugly:
                    idx[j] += 1
                    values[j] = ugly[idx[j]] * primes[j]
        return ugly[-1]
      

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ugly(n, 1);
        vector<int> idx(primes.size(), 0);
        vector<long> values(primes.begin(), primes.end());
        for (int i = 1; i < n; ++i) {
            long next_ugly = *min_element(values.begin(), values.end());
            ugly[i] = (int)next_ugly;
            for (int j = 0; j < primes.size(); ++j) {
                if (values[j] == next_ugly) {
                    idx[j]++;
                    values[j] = (long)ugly[idx[j]] * primes[j];
                }
            }
        }
        return ugly[n-1];
    }
};
      

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int[] idx = new int[primes.length];
        int[] values = primes.clone();
        for (int i = 1; i < n; i++) {
            int nextUgly = Integer.MAX_VALUE;
            for (int v : values) nextUgly = Math.min(nextUgly, v);
            ugly[i] = nextUgly;
            for (int j = 0; j < primes.length; j++) {
                if (values[j] == nextUgly) {
                    idx[j]++;
                    values[j] = ugly[idx[j]] * primes[j];
                }
            }
        }
        return ugly[n - 1];
    }
}
      

var nthSuperUglyNumber = function(n, primes) {
    let ugly = [1];
    let idx = new Array(primes.length).fill(0);
    let values = primes.slice();
    for (let i = 1; i < n; i++) {
        let nextUgly = Math.min(...values);
        ugly.push(nextUgly);
        for (let j = 0; j < primes.length; j++) {
            if (values[j] === nextUgly) {
                idx[j]++;
                values[j] = ugly[idx[j]] * primes[j];
            }
        }
    }
    return ugly[ugly.length - 1];
};
      

Problem Description

The "Super Ugly Number" problem asks you to find the nth super ugly number, given a list of prime numbers primes. A super ugly number is a positive integer whose prime factors are only from the list primes. By convention, 1 is considered a super ugly number. Your task is to generate the sequence of super ugly numbers in ascending order and return the nth element in this sequence.

• Input: An integer n (1 ≤ n ≤ 10⁶), and a list of prime numbers primes (length ≤ 100, each prime ≤ 1000).
• Output: The nth super ugly number.
• Constraints: Each super ugly number must only have prime factors from primes. The sequence must be in ascending order and contain no duplicates.

Thought Process

At first glance, generating all possible products of the given primes and sorting them to find the nth smallest seems straightforward. However, this approach quickly becomes infeasible as n grows large, due to the exponential number of combinations. We need a method to build the sequence incrementally, always keeping it sorted and avoiding duplicates.

The classic "Ugly Number" problem (where the prime set is [2,3,5]) is typically solved using dynamic programming with pointers for each prime. We can generalize this technique: for each prime, keep track of which previous super ugly number to multiply by that prime next. By always picking the minimum candidate, we build the sequence in order, efficiently and without duplicates.

Solution Approach

We use a dynamic programming approach with multiple pointers, one for each prime in the list. The idea is to incrementally build an array of the first n super ugly numbers.

1. Initialization:
   • Create an array ugly to store the super ugly numbers, initialized with 1 as the first element.
   • For each prime, keep an index pointer idx (all start at 0), indicating which element in ugly to multiply by that prime next.
   • Maintain an array values, where values[i] is the next candidate super ugly number for primes[i] (initialized as primes[i]).
2. Iterative Generation:
   • For each position from 1 to n-1 in ugly:
   • Find the minimum value among all values — this is the next super ugly number.
   • Append this number to ugly.
   • For each prime whose candidate equals the minimum, increment its pointer and update its candidate value to the next possible product.
   • This ensures no duplicates and keeps the sequence ordered.
3. Return:
   • After filling ugly up to n elements, return ugly[n-1].

This approach leverages the fact that every super ugly number can be produced by multiplying a previous super ugly number by one of the primes, and by always choosing the smallest next candidate, we maintain order and avoid unnecessary computation.

Example Walkthrough

Let's walk through the process for n = 12 and primes = [2, 7, 13, 19]:

1. Initialize ugly = [1], idx = [0, 0, 0, 0], values = [2, 7, 13, 19].
2. Step 1: Next min is 2. Append 2 to ugly. Increment idx[0] to 1. Now, values[0] = ugly[1] * 2 = 4.
3. Step 2: Next min is 4. Append 4. Increment idx[0] to 2. values[0] = ugly[2] * 2 = 8.
4. Step 3: Next min is 7. Append 7. Increment idx[1] to 1. values[1] = ugly[1] * 7 = 14.
5. Step 4: Next min is 8. Append 8. Increment idx[0] to 3. values[0] = ugly[3] * 2 = 14.
6. Step 5: Next min is 13. Append 13. Increment idx[2] to 1. values[2] = ugly[1] * 13 = 26.
7. Step 6: Next min is 14 (from both 2*7 and 7*2). Append 14. Increment both idx[0] and idx[1] to 4 and 2. Update values[0] = ugly[4]*2=16, values[1]=ugly[2]*7=28.
8. Continue this process until 12 numbers are generated: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]. The 12th is 32.

Each step, we only consider the next possible multiples, never missing or repeating a value.

Time and Space Complexity

Brute-force approach:

• Would attempt to generate all products of primes up to the nth number, which is exponential and infeasible for large n.

• Each of the n super ugly numbers is generated in a loop, and for each, we scan through k primes to update pointers and candidates. Thus, total time complexity is O(nk), where k is the number of primes.
• Space complexity is O(n + k): O(n) for the ugly number list, O(k) for indices and candidate values.

Since both n and k are constrained (n ≤ 10⁶, k ≤ 100), this is efficient enough for practical use.

Summary

The Super Ugly Number problem is an elegant extension of the classic Ugly Number sequence, generalized to any set of primes. By using dynamic programming with pointers for each prime, we efficiently generate the sequence in order, ensuring no duplicates, and can quickly find the nth super ugly number. The key insight is to always multiply the next candidate for each prime and take the minimum, which keeps the process both correct and efficient.