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 /ugly_number2.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'ugly_number2.py')
-rw-r--r-- | ugly_number2.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/ugly_number2.py b/ugly_number2.py new file mode 100644 index 0000000..a2906e1 --- /dev/null +++ b/ugly_number2.py @@ -0,0 +1,28 @@ +# 264. Ugly Number II + +""" +an ugly number is a positive integer whose prime factors are limited to +2,3,5. given an integer 'n', return the n'th ugly number +""" + + +class Solution(object): + def nthUglyNumber(self, n): + """ + :type n: int + :rtype: int + """ + factors, k = [2, 3, 5], 3 + starts, Numbers = [0] * k, [1] + for i in range(n - 1): + candidates = [factors[i] * Numbers[starts[i]] for i in range(k)] + new_num = min(candidates) + Numbers.append(new_num) + starts = [starts[i] + (candidates[i] == new_num) for i in range(k)] + return Numbers[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.nthUglyNumber(10)) + print(obj.nthUglyNumber(1)) |