| Beats 99.69 % of the Solutions | C++ | Python3 | 🔥🔥🔥 |
Intuition\nThe problem is to find the nth super ugly number, which is a number whose prime factors are restricted to a given set of primes. To generate these nu
# Intuition\nThe problem is to find the nth super ugly number, which is a number whose prime factors are restricted to a given set of primes. To generate these numbers in order, the approach leverages dynamic programming with the help of multiple pointers (or indices) to track the smallest multiples of the primes. This ensures we can progressively generate the sequence of super ugly numbers in an efficient manner.\n\n# Approach in C++\n**1. Initialize arrays:**\n-\n\n- **t :** an array to store the first n super ugly numbers, starting with t[0] = 1 since 1 is considered a super ugly number.\n- **_nxt :** an array that tracks the next potential ugly number generated by each prime factor.\n- **ind :** an array that keeps track of which index in the t array is used for generating the next multiple for each prime.\n- \n**2. Initial setup:**\n-\n- Initialize _nxt with the primes, i.e., the first potential ugly numbers are just the primes themselves.\n- Set ind to 0 for all primes since initially, the first ugly number (1) is used to generate the next multiples.\n \n**3. Iterate through to build the list of ugly numbers:**\n-\n- For each i from 1 to n-1, find the minimum value in the _nxt array, which represents the next smallest potential ugly number.\n- Add this minimum value to the t array, marking it as the next ugly number.\n- For each prime that generated this minimum value, update its index in ind and calculate its next multiple by multiplying the prime with the next value in the t array.\n- \n**4. Return the nth ugly number:**\n  -\n- After filling up the t array with n super ugly numbers, return the last element in t, which corresponds to the nth ugly number.\n\n# Complexity\n-  **Time complexity :**\n      -\n   - The outer loop runs n times.\n   - The inner loop that finds the minimum of _nxt and updates it runs m times for each iteration, where m is the number of primes.\n - So, the time complexity is O(n * m).\n\n- **Space complexity :**\n   -\n  - We store the t array of size n and two arrays _nxt and ind of size m.\n  - Thus, the space complexity is O(n + m).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    Solution() {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n        cout.tie(0);\n    }\n\n    int nthSuperUglyNumber(int n, vector<int>& p) {\n        long long t[n+1];\n        int m = p.size();\n        long long _nxt[m];\n        int ind[m];\n        for(int i=0;i<m;i++)\n        {\n            _nxt[i] = p[i];\n            ind[i] = 0;\n        }\n        t[0] = 1;\n        long long nxt = 1;\n        for(int i=1;i<n;i++)\n        {\n            nxt = INT_MAX;\n            for(int j=0;j<m;j++)\n                nxt = min(nxt, _nxt[j]);\n            t[i] = nxt;\n            for(int j=0;j<m;j++)\n            {\n                if(nxt == _nxt[j])\n                {\n                    ind[j]++;\n                    _nxt[j] = t[ind[j]] * p[j];\n                }\n            }\n        }\n        return nxt;\n    }\n};\n```\n# Summary\nThis approach efficiently calculates the nth super ugly number by maintaining multiple pointers to track the current multiples of each prime. By finding the minimum of the next possible ugly numbers at each step, it ensures the correct sequence is generated while avoiding repeated calculations.\n\n# Approach in Python3\n**1. Initialize Results and Indices:**\n   -\n- Start by creating a list res to store the super ugly numbers. Initialize it with the number 1, because the first super ugly number is always 1.\n- Create two index lists: ind, which stores the prime indices for comparison, and _ind, which keeps track of the indices of the prime multiples used to generate the next ugly number.\n\n**2. Priority Queue (Min-Heap):**\n   -\nA priority queue (min-heap) pq is used to efficiently retrieve the smallest possible super ugly number in each iteration.\nInitially, the heap is populated with tuples (prime_value, prime_index), where each prime_value is the prime from the input array p, and prime_index is its corresponding index.\n\n**3. Generating the Sequence:**\n   -\n- For each iteration up to n-1 (since we already have the first ugly number), do the following:\n- Pop the smallest prime number from the heap (i.e., pr) and its associated index (i).\n- Append this prime pr to the result list res.\n- Increment the usage count (_ind[i]) for the current prime index i.\n- Ensure that the next value to be pushed into the heap is the next valid multiple of the prime (i.e., p[i] * res[_ind[i]]).\n- Push this new value into the heap for further iterations.\n\n**4. Avoiding Duplicates:**\n   -\n- The loop inside the heap processing ensures that the index _ind[i] is incremented until the corresponding prime index is less than or equal to i, which helps to avoid duplicates in the result list.\n\n**5. Return the Result:**\n  -\n- After processing all n-1 iterations, the result list res contains all the super ugly numbers in order. The function returns the last value of the list, which is the nth super ugly number.\n\n# Code\n```py []\nclass Solution:\n    def nthSuperUglyNumber(self, n: int, p: List[int]) -> int:\n        res = [1]\n        ind = [0]\n        _ind = [0 for _ in range(len(p))]\n        pq = [(pr, i) for i, pr in enumerate(p)]\n        heapq.heapify(pq)\n        for _ in range(n - 1):\n            pr, i = heapq.heappop(pq)\n            res.append(pr)\n            ind.append(i)\n            _ind[i] += 1\n            while ind[_ind[i]] > i:\n                _ind[i] += 1\n            heapq.heappush(pq, (p[i] * res[_ind[i]], i))\n        return res[-1]\n\n```\n\n# Complexity\n\n- Time Complexity:\n  -\n  - Each iteration (which happens n-1 times) involves popping from the heap and pushing a new element, which takes O(log k) time where k is the length of primes.\n  - Therefore, the overall time complexity is O(n log k), where n is the number of super ugly numbers required and k is the number of primes.\n\n- Space Complexity:\n   -\n  - The space used is primarily by the heap and the result list. Both structures have at most O(n + k) elements, leading to an overall space complexity of O(n + k).\n\n# Summary \nThis solution efficiently generates the nth super ugly number using a min-heap (priority queue) to always find the next smallest super ugly number in O(log k) time, where k is the number of primes. The key idea is to track the smallest possible multiple of each prime and update the result list in each iteration. The solution leverages both dynamic programming and heap-based optimization to ensure that the computation is performed within the constraints.\n
['C++']