Skip to main content

264. Ugly Number II

medium

Generate the nth ugly number (a positive integer whose prime factors are only 2, 3, and 5). The classic three-pointer DP — or alternatively a min-heap. A clean test of merge-like reasoning.

By Sam K., Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 1 <= n <= 1690

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force (test each integer for ugliness) is too slow because ugly numbers get sparse.

Hint 2

Min-heap: start with {1}, repeatedly pop the smallest x and push x*2, x*3, x*5 — dedup with a set. O(n log n) time, O(n) space.

Hint 3

Better: three-pointer DP. ugly[0] = 1; maintain pointers i2 = i3 = i5 = 0 into the array.

Hint 4

ugly[k] = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5). Advance whichever pointers produced the minimum (could be more than one — handle ties so 6 isn't added twice).

Solution approach

Reveal approach

Three-pointer DP. Allocate ugly[0..n-1]; set ugly[0] = 1. Maintain three pointers i2 = i3 = i5 = 0 into the array. For k from 1 to n-1: candidate2 = ugly[i2]*2; candidate3 = ugly[i3]*3; candidate5 = ugly[i5]*5. ugly[k] = min(candidate2, candidate3, candidate5). Then increment every pointer whose candidate equals ugly[k] — this dedups (6 would otherwise be added by both i2 and i3). Return ugly[n-1]. O(n) time, O(n) space. Heap variant: push 1; repeatedly pop the min x and push x*2, x*3, x*5 (dedup with a hash set). O(n log n) time, O(n) space. The DP wins on constants.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dynamic-programming
  • math
  • heap
  • merge

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More Math practice problems

See all Math problems →