1
# Runtime: 354 ms (Top 28.01%) | Memory: 13.9 MB (Top 55.93%)
2
import heapq
3

4

5
class Solution:
6
    def nthUglyNumber(self, n: int) -> int:
7
        h1, h2, h3 = [], [], []
8
        heapq.heappush(h1, 1)
9
        heapq.heappush(h2, 1)
10
        heapq.heappush(h3, 1)
11
        ugly_number = 1
12
        last_ugly_number = 1
13
        count = 1
14
        while count < n:
15
            if 2 * h1[0] <= 3 * h2[0] and 2 * h1[0] <= 5 * h3[0]:
16
                # pop from h1
17
                x = heapq.heappop(h1)
18
                ugly_number = 2 * x
19
                if ugly_number == last_ugly_number:
20
                    # do nothing
21
                    continue
22
                count += 1
23
                last_ugly_number = ugly_number
24
                heapq.heappush(h1, ugly_number)
25
                heapq.heappush(h2, ugly_number)
26
                heapq.heappush(h3, ugly_number)
27

28
            elif 3 * h2[0] <= 2 * h1[0] and 3 * h2[0] <= 5 * h3[0]:
29
                # pop from h2
30
                x = heapq.heappop(h2)
31
                ugly_number = 3 * x
32
                if ugly_number == last_ugly_number:
33
                    continue
34
                count += 1
35
                last_ugly_number = ugly_number
36
                heapq.heappush(h1, ugly_number)
37
                heapq.heappush(h2, ugly_number)
38
                heapq.heappush(h3, ugly_number)
39
            else:
40
                # pop from h3
41
                x = heapq.heappop(h3)
42
                ugly_number = 5 * x
43
                if ugly_number == last_ugly_number:
44
                    continue
45
                count += 1
46
                last_ugly_number = ugly_number
47
                heapq.heappush(h1, ugly_number)
48
                heapq.heappush(h2, ugly_number)
49
                heapq.heappush(h3, ugly_number)
50

51
        return last_ugly_number