Ugly Number II Python Solution with Tests

Tested Python solution for LeetCode 264 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 264, Medium. Topics: Hash Table, Math, Dynamic Programming, Heap (Priority Queue). View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 264   # by problem number
lcpy gen -s ugly_number_ii   # by problem name

​

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*.

​

Examples

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.

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(n)
    def nth_ugly_number(self, n: int) -> int:
        ugly = [0] * n
        ugly[0] = 1
        i2 = i3 = i5 = 0
        for i in range(1, n):
            next2, next3, next5 = ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5
            nxt = min(next2, next3, next5)
            ugly[i] = nxt
            if nxt == next2:
                i2 += 1
            if nxt == next3:
                i3 += 1
            if nxt == next5:
                i5 += 1
        return ugly[n - 1]

​

Complexity

Time	Space
O(n)	O(n)

​

Tags

NeetCode All.