aboutsummaryrefslogtreecommitdiff
path: root/ugly_number2.py
blob: a2906e1c5bc761975c6899a53fb2695834bb8cb5 (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
# 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))