✅ C++ detailed explanation - beats 98% (Easy approach)
Intuition\nThe problem requires generating the nth super ugly number, which is a positive integer that is a multiple of a given set of prime numbers. We need to
# Intuition\nThe problem requires generating the nth super ugly number, which is a positive integer that is a multiple of a given set of prime numbers. We need to find an efficient approach to generate these super ugly numbers in ascending order.\n\n# Approach\nTo solve this problem, we use a dynamic programming approach. We maintain an array `uglyNumbers` to store the generated super ugly numbers. We initialize it with the first two numbers, 0 and 1. We also create a vector of pairs, `primeIndices`, to keep track of the prime factors and their current indices.\n\nWe iterate from `i = 2` up to `n`, where `n` is the desired index of the super ugly number to generate. For each `i`, we find the next smallest super ugly number among the multiples of the given prime factors using the `primeIndices` vector. We store this value in the `uglyNumbers` array.\n\nWe then update the indices in the `primeIndices` vector based on which prime factor was chosen to generate the current super ugly number.\n\nFinally, we return the nth super ugly number stored in the `uglyNumbers` array.\n\n# Complexity\n- Time complexity: $$O(n * k)$$, where n is the index of the super ugly number to generate and k is the number of prime factors.\n- Space complexity: $$O(n)$$, where n is the index of the super ugly number to generate.\n\n# Code\n```\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        long long uglyNumbers[n + 1];  // Array to store super ugly numbers\n        uglyNumbers[0] = 0;  // Not mandatory, just for clarity\n        uglyNumbers[1] = 1;  // The first super ugly number is 1\n\n        // Create a vector of pairs to store prime factors and their indices\n        vector<pair<int, int>> primeIndices;\n        for (int i = 0; i < primes.size(); i++) {\n            primeIndices.push_back(make_pair(primes[i], 1));\n        }\n\n        for (int i = 2; i <= n; i++) {\n            long long nextUgly = LLONG_MAX;  // Initialize nextUgly to a large value\n            for (int j = 0; j < primes.size(); j++) {\n                // Find the next smallest super ugly number among primes\' multiples\n                nextUgly = min(nextUgly, uglyNumbers[primeIndices[j].second] * (long long)primeIndices[j].first);\n            }\n            uglyNumbers[i] = nextUgly;  // Store the next super ugly number\n            \n            // Update the indices based on which prime factor was chosen\n            for (int j = 0; j < primes.size(); j++) {\n                if (nextUgly == uglyNumbers[primeIndices[j].second] * (long long)primeIndices[j].first) {\n                    primeIndices[j].second++;\n                }\n            }\n        }\n        \n        return uglyNumbers[n];  // Return the nth super ugly number\n    }\n};\n\n```
['Array', 'Math', 'C++']