Problem 264

Abstract / Summary

Generate the nth ugly number which is only divisible by 2, 3, or 5.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0264.py

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        next = [ 1 ]

        for _ in range(n - 1):
            current = heappop(next)
            while next and next[0] == current:
                heappop(next)

            heappush(next, current * 2)
            heappush(next, current * 3)
            heappush(next, current * 5)

        return next[0]
14 lines | 385 bytes | submitted August 19, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 50% (1+ million submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • Hash Table
  • Heap (Priority Queue)
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the n-th ugly number-an integer whose prime factors are limited to 2, 3, and 5. It employs a min-heap to generate ugly numbers in ascending order while automatically discarding duplicates. The algorithm proceeds by repeatedly extracting the smallest candidate, expanding it with the allowed multipliers, and maintaining the heap invariant.

Initialization

next = [1]

A list containing the first ugly number, 1, is created and will serve as the underlying container for the heap. By initializing the heap with a single element, the algorithm guarantees a valid starting point for subsequent extraction and insertion operations.

Main Generation Loop

for _ in range(n - 1):
    current = heappop(next)
    # duplicate removal and insertion follow

The loop iterates exactly n - 1 times because the first ugly number is already present. In each iteration the smallest element is removed from the heap, representing the next ugly number in the ordered sequence.

Duplicate Elimination

while next and next[0] == current:
    heappop(next)

After extracting the current smallest value, the code checks whether the next element in the heap equals the same value. If so, it continues popping until the top of the heap differs. This construct ensures that repeated values-arising from different multiplication paths-are not processed multiple times, thereby preserving uniqueness in the generated sequence.

Insertion of New Candidates

heappush(next, current * 2)
heappush(next, current * 3)
heappush(next, current * 5)

The three allowed prime factors are applied to the extracted ugly number, and the resulting products are inserted back into the heap. Because the heap maintains a sorted order, these new candidates will be considered in proper ascending order during future iterations.

Edge Cases Handled

When the input n equals 1, the loop body is never executed because the range evaluates to zero iterations. The function then directly returns next[0], which is the initial value 1, correctly handling the smallest possible request. The duplicate elimination step also implicitly handles cases where multiple generation paths converge on the same number-for example, 6 can be produced as 2 × 3 or 3 × 2. By removing subsequent identical entries, the algorithm avoids counting such numbers twice.

Performance Optimizations

The use of a min-heap provides an efficient mechanism for always retrieving the smallest pending ugly number without scanning the entire collection. By pushing only the three direct multiples of each extracted value, the algorithm limits the growth of the heap to a manageable size, avoiding the explosion that would occur if all possible combinations were generated indiscriminately. The duplicate removal loop prevents the heap from accumulating redundant entries, which reduces both the number of heap operations and the memory footprint. Together, these choices keep the execution focused on the essential candidates needed to reach the n-th ugly number.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a magical basket that starts with the number one inside. This basket is very special because it likes to grow by playing with the numbers two, three, and five. To find the next number in line, the basket looks at the smallest number currently sitting inside. It takes that tiny number out and creates three new versions of it by multiplying it by two, three, and five. These new results are tossed back into the basket to grow even more later. Because the basket might end up with the same number a few different times, it carefully checks to make sure no duplicates are sitting around. This process happens over and over again like a repeating game. Every time the basket repeats this step, a new number gets generated until reaching the specific spot being searched for. The basket keeps the smallest results organized so that the right number always pops out at the end.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.59 | σ = 1.97

Complexity Analysis

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python JS Java C# Go
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
fengvyi C++
fpdjsns C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fengvyi C++
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
zfang399 C++
44 links | 29 authors | 9 languages

Videos

17 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

4 similar problems

Solved On The Same Day

2 easy 6 medium 1 hard
10 solutions   August 19, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality