1
// Finds the nth super ugly number given a list of prime numbers.
2

3
class Solution {
4
 public:
5
  int nthSuperUglyNumber(int n, vector<int> &primes) {
6
    if (n == 1) return 1;
7

8
    int numPrimes = primes.size(); // Number of prime numbers
9
    vector<int> primeIndices(numPrimes,
10
                             0); // Indices to track prime number multiples
11

12
    int superUgly[n]; // Array to store super ugly numbers
13
    // memset(superUgly, 0, sizeof(superUgly));  // Initialize the array
14
    // (commented out since it's unnecessary)
15
    superUgly[0] = 1; // First super ugly number is always 1
16

17
    for (int i = 1; i < n; i++) {
18
      long minVal = INT_MAX; // Minimum value among the prime number multiples
19

20
      // Find the minimum value among the prime number multiples
21
      for (int j = 0; j < numPrimes; j++) {
22
        minVal = min(minVal, (long)primes[j] * superUgly[primeIndices[j]]);
23
      }
24

25
      superUgly[i] = (int)minVal; // Store the minimum value as the next super ugly number
26

27
      // Increment the indices for prime number multiples that contribute to the
28
      // minimum value
29
      for (int j = 0; j < numPrimes; j++) {
30
        if (minVal == (long)primes[j] * superUgly[primeIndices[j]]) {
31
          primeIndices[j]++;
32
        }
33
      }
34

35
      // cout<<superUgly[i]<<",";  // Print the current super ugly number
36
      // (commented out for clarity)
37
    }
38

39
    return superUgly[n - 1]; // Return the nth super ugly number
40
  }
41
};