[LeetCode] 313. Super Ugly Number

Problem : https://leetcode.com/problems/super-ugly-number/

Ugly Number A = Ugly Number B * Prime Number

Consider each prime number is assigned to a list. Then the problem becomes merge multiple ugly number list. We need to generate ugly number on each list on the fly.

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        idx = [0] * len(primes)
        dp = [2**31 - 1] * n
        dp[0] = 1
        
        for i in range(1, n):
            # next ugly number = the minimal number generated by one prime
            # multiple the previous ulgy number
            for j, p in enumerate(primes):
                dp[i] = min(dp[i], p * dp[idx[j]])
                
            for j, p in enumerate(primes):
                # there could be multiple primes
                # generate current minimal number
                # increase idx for all of them
                if dp[i] ==  p * dp[idx[j]]:
                    idx[j] += 1
       
        return dp[-1]