Show problems as
Classic problem #264MediumHash TableMathDynamic ProgrammingHeap (Priority Queue)

Ugly Number II

Real-world version: Nth Smallest Pulley Factor
Tracked in this browser only
Read Ugly Number II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop assembles pulley blocks out of stages. One stage doubles the drive, another triples it and a third quintuples it, and a block may stack any number of stages in any mix, including no stages at all.

Call a positive integer a reachable factor when some stack of stages multiplies out to exactly that integer. A block with no stages leaves the drive alone, so the smallest reachable factor is one.

Sort the reachable factors into increasing order with no repeats, and return the one in position n, counting the smallest as position 1.

Examples

Example 1

Input
n = 7
Output
8

The reachable factors below 8 are 1, 2, 3, 4, 5 and 6, six of them, so 8 lands in position 7. No stack reaches 7, because a stage never multiplies by 7.

Example 2

Input
n = 9
Output
10

Between 6 and 10 the only reachable factors are 8 and 9, so 10 lands in position 9. A doubling stage on top of a quintupling stage gives 10.

Example 3

Input
n = 2
Output
2

Position 1 holds the empty stack, which leaves the factor at 1, so a single doubling stage puts 2 in position 2.

Example 4

Input
n = 20
Output
36

Two doubling stages and two tripling stages multiply out to 36, and exactly 19 reachable factors are smaller than it.

Example 5

Input
n = 40
Output
144

Four doubling stages and two tripling stages multiply out to 144, and exactly 39 reachable factors are smaller than it.

Constraints

  • 1 <= n <= 1690

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nth_ugly_number(n: int) -> int:
Java
public int nthUglyNumber(int n)

More on the same topics