313: Space 96.61%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\nThe idea of this problem is similar to the Ugly Number II problem. We s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\nThe idea of this problem is similar to the Ugly Number II problem. We start with the smallest super ugly number, which is 1. Then, we generate each subsequent super ugly number by multiplying each prime number in the array with the previously generated super ugly numbers, and choosing the smallest one.\n\nWe can maintain a list of indices, one for each prime number, indicating the index of the last super ugly number that was multiplied by that prime number. We use these indices to avoid generating duplicates.\n\nAlgorithm:\n\n1. Initialize a list dp of size n to store the first n super ugly numbers.\n2. Initialize a list idx of size k, where k is the length of primes, to store the index of the last super ugly number that was multiplied by each prime number. Initialize each element of idx to 0.\n3. Initialize a list nums of size k to store the product of each prime number with the previously generated super ugly numbers. Initialize each element of nums to the corresponding prime number.\n4, Initialize a variable i to 1, representing the index of the next super ugly number to be generated.\n5. While i < n:\na. Generate the ith super ugly number by choosing the minimum number in nums, and add it to dp.\nb. For each j from 0 to k-1, if nums[j] is equal to the ith super ugly number, increment idx[j] by 1 and update nums[j] to be primes[j] times dp[idx[j]].\nc. Increment i by 1.\n6. Return the last element of dp.\n\nTime Complexity: O(nk), where n is the input integer and k is the length of the primes array.\n\nSpace Complexity: O(n+k), where n is the input integer and k is the length of the primes array.\n\n# Complexity\n- Time complexity:\n65.62%\n\n- Space complexity:\n96.61%\n\n# Code\n```\nclass Solution:\n    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n        # create a list to store the super ugly numbers, initialize with 1\n        super_ugly = [1]\n        # create a list to store the indices for each prime number\n        idx = [0] * len(primes)\n        # create a list to store the product of prime numbers with their corresponding indices\n        # this will be used to find the next super ugly number\n        prod = [p for p in primes]\n        \n        # loop until we find the nth super ugly number\n        while len(super_ugly) < n:\n            # find the minimum value in prod, which will be the next super ugly number\n            next_ugly = min(prod)\n            # append it to the list of super ugly numbers\n            super_ugly.append(next_ugly)\n            \n            # update the index for each prime number whose product is equal to next_ugly\n            for i in range(len(primes)):\n                if next_ugly == prod[i]:\n                    idx[i] += 1\n                    prod[i] = primes[i] * super_ugly[idx[i]]\n        \n        # return the last element in the list of super ugly numbers, which is the nth super ugly number\n        return super_ugly[-1]\n\n```
['Array', 'Math', 'Dynamic Programming', 'Python', 'Python3']