aboutsummaryrefslogtreecommitdiff
path: root/super_ugly_num.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /super_ugly_num.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'super_ugly_num.py')
-rw-r--r--super_ugly_num.py28
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