0403MediumHash TableMathDynamic ProgrammingHeap (Priority Queue)

Nth Smallest Pulley Factor

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def nth_ugly_number(n: int) -> int:

Java

public int nthUglyNumber(int n)

The intended approach

Time O(n)Space O(n) for the table of factors that is built

Grow the sorted list of reachable factors one entry at a time. Keep three cursors into the list already built, one per stage, each marking the earliest factor that has not yet been multiplied by that stage. The next entry is the smallest of the three candidate products, and every cursor whose candidate matched that smallest value advances, which is what keeps repeats such as 2 * 3 and 3 * 2 from both being appended.

Pythonentry point: nth_ugly_number

def nth_ugly_number(n):
    # Time O(n): each of the n table slots costs three multiplications and a
    # three-way comparison. Space O(n) for the table that is built up.
    table = [0] * n
    table[0] = 1
    at2 = 0
    at3 = 0
    at5 = 0
    for k in range(1, n):
        by2 = table[at2] * 2
        by3 = table[at3] * 3
        by5 = table[at5] * 5
        best = by2
        if by3 < best:
            best = by3
        if by5 < best:
            best = by5
        table[k] = best
        if by2 == best:
            at2 += 1
        if by3 == best:
            at3 += 1
        if by5 == best:
            at5 += 1
    return table[n - 1]

The obvious version

Run a min-heap seeded with 1, popping the smallest pending factor n times and pushing its double, triple and quintuple, with a set guarding against pushing the same factor twice.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

import heapq


def bf_nth_ugly_number(n):
    pending = [1]
    known = {1}
    value = 1
    for _ in range(n):
        value = heapq.heappop(pending)
        for stage in (2, 3, 5):
            grown = value * stage
            if grown not in known:
                known.add(grown)
                heapq.heappush(pending, grown)
    return value

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in