Python simple to understand DP with heapq, beats 95.56% (292 ms)
The essence of this problem is to inserting elements into an array with some pattern while keep the array sorted.\n\nUse the given primes example [2,7,13,19]\n\
The essence of this problem is to inserting elements into an array with some pattern while keep the array sorted.\n\nUse the given primes example [2,7,13,19]\n\n- At first step, we add 1 to the array since the first ugly number is 1, we have\n\n\tarray = [1]\n\n- Then we use the smallest newly added element to multiply all given primes numbers and add it to the array\n\n\tarray = [1, 1x2, 1x7,1x13,1x19] = [1,2,7,13,19]\n\n- Since 2 is the smallest newly added element, so next step we need to add [2x2, 2x7,2x13,2x19], note that since 2x2 less than 1x7, so the resulting sorted array is:\n\n\tarray = [1, 2, 4, 7, 13, 14, 19, 26, 38], then we use 4 to multiple primes as the next step.\n\nI found that the number I use to multiple with the primes is exactly the number (n-1)^th ugly number. So it\'s trival to solve it recursively:\n\n```python\ndef nthSuperUglyNumber(self, n: int, primes) -> int:\n\tl = [1]\n\td = defaultdict(lambda: False)\n\td[1] = True\n\tdef recur(n):\n\t\tif n == 1:\n\t\t\treturn 1\n\t\telse:\n\t\t\tlast = recur(n-1)\n\t\t\tfor p in primes:\n\t\t\t\tnum = p*last\n\t\t\t\tif num > l[-1]:\n\t\t\t\t\tl.append(num)\n\t\t\t\t\td[num] = True\n\t\t\t\telse:\n\t\t\t\t\tif not d[num]:\n\t\t\t\t\t\tbisect.insort_left(l, num)\n\t\t\t\t\t\td[num] = True\n\t\t\treturn l[n-1]\n        return recur(n)\n```\n\nHowever, it easily fails at 81 / 83, because of python\'s RecursionError: maximum recursion depth exceeded in comparison. It\'s pretty annoying you find a solution but it exceeds the time limit. So I tried using an iteration approach:\n\n```python\ndef nthSuperUglyNumber(self, n: int, primes) -> int:\n\tpq = []\n\td = defaultdict(lambda: False)\n\tpq = [1]\n\td[1] = True\n\tfor i in range(0, n):\n\t\tfor p in primes:\n\t\t\tr = p*pq[i]\n\t\t\tif not d[r]:\n\t\t\t\tif r > pq[-1]:\n\t\t\t\t\tpq.append(r)\n\t\t\t\telse:\n\t\t\t\t\tbisect.insort_left(pq, r)\n\t\t\t\td[r] = True\n\treturn pq[n-1]\n```\n\nIt indeed avoids the curse of recursion but still TLE on 81/83 because of the overhead of adding way more elements than we actually need and maintaining the order of them. So the last hope is dp, (should be the first).\n\nHowever, it does require some deep thoughts than brute force with recursion. Note that since elements are products with each other or with itself. i.e. the first one is 1, is the min of all primes of power 0. The second element is min of all elements of power 1. Starting from the third, we have to compare 2^2 with 7^1 in the given example, or 2^2 with 3^1, if the second given prime number is 3. It\'s not easy to get the pattern since the order depends on the difference/distance between the given prime numbers. Using a table to illustrate the final given example [2,7,13,19] when n=12.\n\n```\n2^1  7^1*1      13^1*1    19^1*1\n2^2  7^1*2^1    13^1*2^1\n2^3  7^1*2^2\n2^4 \n2^5\n```\n\nNote that the first element is special since the smallest value it can get given a under a certain power constrain is to multiply by itself. Starting from the second one, it actually grows with itself multiply by the ith ugly number given by its row e.g. the third row of 7 is 7 * array[2] (zero based), which is 7\\*4 = 28. Based on this observation, we can add one number at a time until we hit n.\n\n```python\ndef nthSuperUglyNumber(self, n: int, primes) -> int:\n\tlp = len(primes)\n\tindices = [0]*lp\n\tl = [1]*n\n\tpq = list(zip(primes, range(lp)))\n\theapq.heapify(pq)\n\tc, mx = 1, 1\n\twhile c < n:\n\t\tval, i = heapq.heappop(pq)\n\t\tindices[i] += 1\n\t\tif val > mx:\n\t\t\tl[c] = val\n\t\t\tmx = val\n\t\t\tc += 1\n\t\tif i == 0:\n\t\t\tval *= primes[i]\n\t\telse:\n\t\t\tval = primes[i] * l[indices[i]]\n\t\theapq.heappush(pq, (val, i))\n        return l[-1]\n```\n\nWe use a min priority queue to keep the different values in order and pop up the lowest value we should add to the array, after added, we push it back to the pq. In order to know how to update the value, we also saved it\'s index in primes, so that we can know which number it should multiply to as the next val when it pops out. Fortunately the size of the primes is small so the cost of using priority queue is acceptable.\n\nIt\'s not a straight forward problem, I did spend quite some time to figure this out. Hope it helps.\n\n\n
['Dynamic Programming', 'Heap (Priority Queue)', 'Python', 'Python3']