C++| Dynamic programming (DP) |
Intuition\n Describe your first thoughts on how to solve this problem. Upon analyzing the code, here are my initial thoughts on how to solve the problem:\n\n1. 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->Upon analyzing the code, here are my initial thoughts on how to solve the problem:\n\n1. Understand the problem: The goal is to find the nth super ugly number given a list of prime numbers. A super ugly number is a positive integer whose prime factors are limited to the given list of primes.\n\n2. Approach: The code follows a dynamic programming approach. It uses an array, `superUgly`, to store the super ugly numbers. The algorithm iterates from 1 to n, calculating each super ugly number based on the prime number multiples and their corresponding indices.\n\n3. Key variables:\n   - `n`: The input representing the position of the super ugly number to find.\n   - `primes`: A vector containing the prime numbers to be used as factors.\n   - `numPrimes`: The number of prime numbers in the `primes` vector.\n   - `primeIndices`: A vector storing the current indices for each prime number.\n   - `superUgly`: An array that will hold the super ugly numbers.\n\n4. Algorithm:\n   - Check if n is 1, in which case the first super ugly number is 1.\n   - Initialize the vector `primeIndices` with zeros for each prime number.\n   - Initialize the first element of `superUgly` as 1 since 1 is always a super ugly number.\n   - Iterate from 1 to n (exclusive):\n     - Find the minimum value, `minVal`, among the prime number multiples.\n     - Store `minVal` as the current super ugly number.\n     - Increment the indices of the prime number multiples that contribute to the minimum value.\n   - Return the nth super ugly number.\n\nOverall, the code efficiently calculates the nth super ugly number by iteratively finding the minimum value among the prime number multiples.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->To solve the problem of finding the nth super ugly number given a list of prime numbers, here\'s the approach I would take:\n\n1. Initialize a list or array to store the super ugly numbers.\n2. Since the first super ugly number is always 1, add it to the list.\n3. Create a separate list to keep track of the indices for each prime number in the given list. Initialize all indices to 0.\n4. Iterate from 1 to n (exclusive) to find the remaining super ugly numbers.\n5. For each iteration:\n   a. Find the minimum value among the products of each prime number with its corresponding super ugly number at the respective index.\n   b. Add the minimum value to the list of super ugly numbers.\n   c. Update the indices for the prime numbers that contributed to the minimum value by incrementing them.\n   d. Repeat steps a-c until all n super ugly numbers are found.\n6. Return the nth super ugly number from the list.\n\nThis approach takes advantage of the fact that each super ugly number can be obtained by multiplying a prime number with a previously generated super ugly number. By keeping track of the indices for each prime number, we can efficiently generate the super ugly numbers in ascending order.\n\n# Complexity\n- Time complexity: O(n * k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n + k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// Finds the nth super ugly number given a list of prime numbers.\n\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        if (n == 1)\n            return 1;\n\n        int numPrimes = primes.size();  // Number of prime numbers\n        vector<int> primeIndices(numPrimes, 0);  // Indices to track prime number multiples\n\n        int superUgly[n];  // Array to store super ugly numbers\n        // memset(superUgly, 0, sizeof(superUgly));  // Initialize the array (commented out since it\'s unnecessary)\n        superUgly[0] = 1;  // First super ugly number is always 1\n\n        for (int i = 1; i < n; i++) {\n            long minVal = INT_MAX;  // Minimum value among the prime number multiples\n\n            // Find the minimum value among the prime number multiples\n            for (int j = 0; j < numPrimes; j++) {\n                minVal = min(minVal, (long)primes[j] * superUgly[primeIndices[j]]);\n            }\n\n            superUgly[i] = (int)minVal;  // Store the minimum value as the next super ugly number\n\n            // Increment the indices for prime number multiples that contribute to the minimum value\n            for (int j = 0; j < numPrimes; j++) {\n                if (minVal == (long)primes[j] * superUgly[primeIndices[j]]) {\n                    primeIndices[j]++;\n                }\n            }\n\n            // cout<<superUgly[i]<<",";  // Print the current super ugly number (commented out for clarity)\n        }\n\n        return superUgly[n - 1];  // Return the nth super ugly number\n    }\n};\n\n```\n![Leetcode.jpeg](https://assets.leetcode.com/users/images/7ad5c196-b2e4-43fd-bd89-e2245f9a1cdb_1688138793.3109202.jpeg)\n
['Array', 'Math', 'Dynamic Programming', 'C++']