diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /super_ugly_num.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'super_ugly_num.py')
-rw-r--r-- | super_ugly_num.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/super_ugly_num.py b/super_ugly_num.py new file mode 100644 index 0000000..278edb3 --- /dev/null +++ b/super_ugly_num.py @@ -0,0 +1,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 |