236. Ugly Number II
An ugly number is a positive integer whose prime factorization uses only the primes 2, 3, and 5. Listed in increasing order they start 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … (with 1 counting as the first, since it has no prime factors at all).
Given an integer n, return the n-th ugly number in that sequence, 1-indexed — so n = 1 yields 1.
Checking numbers one by one is hopeless: ugly numbers thin out quickly, so the trick is to generate the sequence rather than test candidates.
Example 1:
Input: n = 10
Output: 12
Explanation: The sequence in order is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 — the 10th entry is 12. (7 and 11 are skipped: they contain forbidden primes.)
Example 2:
Input: n = 1
Output: 1
Explanation: By convention the sequence starts at 1, so the first ugly number is 1 itself.
Constraints:
- 1 ≤ n ≤ 1690
- The answer always fits in a signed 32-bit integer (the 1690th ugly number is 2123366400).
Hints:
Every ugly number except 1 equals some smaller ugly number multiplied by 2, 3, or 5. That means you can build the sequence from itself.
A min-heap seeded with 1 works: pop the smallest, push its ×2, ×3, ×5 children, and skip duplicates with a hash set. The n-th pop is the answer.
For O(n): keep three indices p2, p3, p5 into the array you are building. The next ugly number is min(u[p2]·2, u[p3]·3, u[p5]·5); advance every index whose product matched (that also swallows duplicates like 6 = 2·3 = 3·2).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 10
Expected output: 12