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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Ugly Number II and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →