Teaching Kids Programming – Using Heap (Priority Queue) to Generate Nth Ugly Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer n, return the nth ugly number. Ugly number is a positive number whose prime factors only include 2, 3, and/or 5.

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 is typically treated as an ugly number.

Generate Nth Ugly Number via Bruteforcing (Try and Check)

Remember that the ugly number is the positive integers that only contain prime factors of 2, 3 and 5. Given that we know how to check if an integer is ugly, we can bruteforce each positive integers and try to count to the nth one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        def isUgly(n):
            if n < 1:
                return False
            while n % 2 == 0:
                n //= 2
            while n % 3 == 0:
                n //= 3
            while n % 5 == 0:
                n //= 5
            return n == 1
        i = 1
        while True:
            if isUgly(i):                
                n -= 1
                if n == 0:
                    return i
            i += 1

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        def isUgly(n):
            if n < 1:
                return False
            while n % 2 == 0:
                n //= 2
            while n % 3 == 0:
                n //= 3
            while n % 5 == 0:
                n //= 5
            return n == 1
        i = 1
        while True:
            if isUgly(i):                
                n -= 1
                if n == 0:
                    return i
            i += 1

The time complexity is O(NLogN) assuming checking if an integer is ugly takes O(LogN) time. The space complexity is O(1).

Using Heap or Priority Queue to Generate the Nth Ugly Number

We can keep the ugly numbers in a heap (or priority queue), then for next ugly number, we pick the smallest ugly number that we have generated so far, and multiply another prime factor of 2, 3, and 5, and if it has not been seen, we push it back to the priority queue (or insert it into the heap).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from heapq import heappop, heappush
 
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        seen = set([1])
        heap = [1]
        for _ in range(n):
            cur = heappop(heap)
            for i in [2, 3, 5]:
                new = cur * i
                if new not in seen:
                    seen.add(new)
                    heappush(heap, new)
        return cur

from heapq import heappop, heappush

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        seen = set([1])
        heap = [1]
        for _ in range(n):
            cur = heappop(heap)
            for i in [2, 3, 5]:
                new = cur * i
                if new not in seen:
                    seen.add(new)
                    heappush(heap, new)
        return cur

The time complexity will thus be roughly O(N) and the space complexity is O(N) as we are using hash set (to remember the ugly numbers we have seen) and the heap (priority queue) to keep tracking the current lowest ugly numbers.

Peeking the root of the heap is O(1) constant but popping it (remove it) and pushing a new element into the heap takes O(LogN) as this requires re-constructing the heap. But this approach is a lot more efficient than the first bruteforce approach because it will only deal with the ugly numbers – it generates next ugly number based on the current smallest ugly number in the pool (heap).

See also: C++ Algorithm to Check Ugly Number

–EOF (The Ultimate Computing & Technology Blog) —