Find the th ugly number, where ugly numbers are positive integers whose prime factors are limited to 2, 3, and 5.
Ugly Number II
An ugly number is a positive integer whose only prime factors are $2, \3, and \5$.
Given an integer , return the th ugly number in the increasing sequence of ugly numbers, where the sequence starts with $1$.
Your task is to generate the sequence efficiently enough to handle moderately large without checking every integer one by one.
Input Format
- A single integer .
- You may assume .
Output Format
- Return a single integer: the th ugly number.
Constraints
- .
- The answer fits in a 32-bit signed integer for the intended test set.
Example 1
Input
n = 10
Output
12
Explanation
The ugly numbers in order are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... so the 10th is 12.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.