Ugly Number II — LeetCode 264 Python Solution

The problem

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.

Example

Input

n = 10

Output

12

Explanation

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Python solution

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1]
        vis = {1}
        ans = 1
        for _ in range(n):
            ans = heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heappush(h, nxt)
        return ans

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 264. Ugly Number II is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems