AlgoMaster Logo

Ugly Number II

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find the nth number in a sequence where every number has only 2, 3, and 5 as prime factors. The sequence starts with 1 (by convention, 1 is ugly since it has no prime factors at all), then 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and so on.

Every ugly number except 1 is generated by multiplying a smaller ugly number by 2, 3, or 5. For example, 4 = 2 2, 6 = 2 3, 8 = 2 4, and 9 = 3 3. The work is generating these numbers in sorted order without gaps or duplicates, which means we need a way to always pick the next smallest ugly number.

Key Constraints:

  • 1 <= n <= 1690 → The upper bound on n is small, so the time complexity is not the constraint here. The harder part is generating the sequence in order without producing the same number twice.
  • The nth ugly number can be large. The 1690th ugly number is 2,123,366,400, which fits in a 32-bit signed integer. The heap approach below pushes the products of every popped value, so it can compute 5 * 2,123,366,400, which overflows 32 bits. That approach uses 64-bit integers for safety. The three-pointer approach never produces a value past the answer, so 32-bit integers are sufficient there.

Approach 1: Min-Heap

Intuition

Instead of testing every integer for ugliness, we can generate ugly numbers directly. Start with 1, the first ugly number. For each ugly number we extract, its multiples by 2, 3, and 5 are also ugly, so we push those three products into a min-heap. The heap always returns the smallest candidate next, which gives us the sequence in sorted order.

Duplicates are the complication. The number 6 can be produced as 2 3 and as 3 2, so the same value reaches the heap from two directions. A set of seen values prevents counting it twice.

Algorithm

  1. Initialize a min-heap with 1 and a set containing 1.
  2. Repeat n times:
    • Extract the smallest value from the heap. This is the next ugly number.
    • For each factor in {2, 3, 5}, compute the product.
    • If the product hasn't been seen before, add it to both the heap and the set.
  3. The nth extracted value is the answer.

Example Walkthrough

1Initialize: heap = {1}, count = 0
0
0
next
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
1/8

Code

The heap approach carries two costs: the log-factor overhead of the heap and a hash set for deduplication. The next approach removes both by tracking three pointers into the ugly number sequence, so each step knows exactly which ugly number to multiply by each factor.

Approach 2: Three Pointers (Dynamic Programming)

Intuition

Every ugly number is one of: 2 (some earlier ugly number), 3 (some earlier ugly number), or 5 * (some earlier ugly number). So we maintain a sorted array of ugly numbers and three pointers: i2, i3, and i5. Each pointer tracks which ugly number in our array should next be multiplied by its respective factor.

At each step, we compute three candidates: ugly[i2] * 2, ugly[i3] * 3, and ugly[i5] * 5. The next ugly number is the minimum of these three. Then we advance whichever pointer or pointers produced that minimum. When two candidates tie (for example 2 3 = 6 and 3 2 = 6), we advance both pointers, which skips the duplicate without a set.

Algorithm

  1. Create an array ugly of size n. Set ugly[0] = 1.
  2. Initialize three pointers: i2 = 0, i3 = 0, i5 = 0.
  3. For each position from 1 to n-1:
    • Compute next2 = ugly[i2] * 2, next3 = ugly[i3] * 3, next5 = ugly[i5] * 5.
    • Set ugly[i] = min(next2, next3, next5).
    • If ugly[i] == next2, increment i2.
    • If ugly[i] == next3, increment i3.
    • If ugly[i] == next5, increment i5.
  4. Return ugly[n - 1].

Example Walkthrough

1Initialize: ugly[0]=1, i2=0, i3=0, i5=0
0
i2
1
i3
i5
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
1/9

Code