Leetcode 313. Super Ugly Number

Problem

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer

Algorithm

Dynamic Programming (DP). Use pointers to save the value of each primes and move the pointer of the small value.

Code

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        dp = [1]
        plen = len(primes)
        pointers = [0] * plen
        size = 0
        while size < n:
            min_val = dp[pointers[0]] * primes[0]
            index = 0
            for i in range(1, plen):
                val = dp[pointers[i]] * primes[i]
                if min_val > val:
                    min_val = val
            dp.append(min_val)
            for i in range(0, plen):
                val = dp[pointers[i]] * primes[i]
                if min_val == val:
                    pointers[i] += 1
            size = size + 1
        return dp[n-1]