Skip to content

264. Ugly Number II

Hash Table Math Dynamic Programming Heap (Priority Queue)

Problem - Ugly Number II

Medium

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 1:

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.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

 

Constraints:

  • 1 <= n <= 1690

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap = [1]
        result = 1
        visited = {1}

        for _ in range(n):
            result = heappop(heap)
            for val in [2, 3, 5]:
                next_val = result * val
                if next_val not in visited:
                    visited.add(next_val)
                    heappush(heap, next_val)

        return result

Submission Stats:

  • Runtime: 83 ms (36.77%)
  • Memory: 18.1 MB (15.05%)