aboutsummaryrefslogtreecommitdiff
path: root/super_ugly_num.py
blob: 278edb3391b3ebd63e69fd7f1903b7e3369a513d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 313. Super Ugly Number

"""
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 n'th super ugly number. the n'th super ugly number is guaranteed
to fit in a 32-bit integer (signed)
"""


class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        size = len(primes)
        ugly, dp, idx, nums = 1, [1], [0] * size, [1]
        for i in range(1, n):
            for j in range(0, size):
                if nums[j] == ugly:
                    nums[j] = dp[idx[j]] * primes[j]
                    idx[j] += 1
            ugly = min(nums)
            dp.append(ugly)
        return dp[-1]


if __name__ == "__main__":
    obj = Solution()
    print(obj.nthSuperUglyNumber(n=12, primes=[2, 7, 13, 19]))  # expect: 32
    print(obj.nthSuperUglyNumber(n=1, primes=[2, 3, 5]))  # expect: 1