Abstract / Summary

Given a list of prime numbers and a target, find the nth smallest number that is divisible by at least one of the primes.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the n-th super ugly number given a list of prime factors. A super ugly number is defined as a positive integer whose prime divisors belong exclusively to the supplied primes array. The algorithm builds the sequence incrementally using a min-heap to always retrieve the smallest candidate that has not yet been emitted. The special case n == 1 is handled explicitly, returning the base value 1 which is universally accepted as the first super ugly number.

Key Steps

The first logical block checks whether the requested position is the first element of the sequence. If so, the function returns immediately:

if n == 1:
    return 1

Next, a copy of the primes list is created and used as the initial heap. Because the original list is sorted, the copy can serve directly as a valid min-heap without additional heapification:

next = primes.copy()   # sorted => can be used as a min-heap instantly

The core of the algorithm is a loop that runs until the counter n has been reduced to 2. Inside the loop the smallest candidate is extracted from the heap:

current = heappop(next)

If the same value appears multiple times at the top of the heap, those duplicates are removed in a nested while-loop. This ensures that each distinct super ugly number is processed only once:

while next and next[0] == current:
    heappop(next)

For the extracted current value, new candidates are generated by multiplying it with every prime factor. Each product is pushed back onto the heap, expanding the pool of future candidates:

for p in primes:
    heappush(next, current * p)

The loop counter n is decremented after each distinct number has been processed:

n -= 1

When the loop terminates, the heap contains the remaining candidates, and the smallest one corresponds to the n-th super ugly number. The final extraction returns this value:

return heappop(next)

Edge Cases

The implementation explicitly handles the scenario where the requested index is 1. By returning 1 immediately, it avoids unnecessary heap operations and respects the definition that 1 is always the first super ugly number regardless of the prime set.

Another subtle edge case is the presence of duplicate values in the heap. Because each multiplication can produce the same product via different factor combinations (for example, 2*3 and 3*2 both yield 6), the inner while-loop that discards consecutive identical entries guarantees that the algorithm does not count the same super ugly number multiple times. This deduplication step also prevents the heap from growing uncontrollably with redundant entries.

The algorithm also works correctly when the primes list contains a single element. In that situation, the heap initially holds one value, and each iteration multiplies the current number by that single prime, effectively generating a geometric progression. The duplicate-removal loop remains harmless because no two identical values can appear consecutively in this specific case.

Performance Optimizations

Using the sorted copy of primes as the initial heap eliminates the need for an explicit heapify call, saving a constant amount of work at startup. The heap data structure itself provides logarithmic insertion and removal, ensuring that each candidate is managed efficiently as the sequence grows.

The duplicate-removal loop is a targeted optimization that prevents the heap from accumulating multiple identical entries. By eliminating these redundancies early, the algorithm reduces the number of heap operations required in later iterations, which in turn lowers the overall runtime overhead.

Generating new candidates by iterating over the original primes list rather than over a dynamically expanding set of factors keeps the inner loop bounded by the size of the input prime array. This design choice avoids the combinatorial explosion that could arise if the algorithm attempted to track all possible factor combinations explicitly.

Building a list of super special numbers is like playing a game where you want to find numbers made only by multiplying a few secret prime numbers together. Imagine you have a tiny magic bag that holds numbers you want to check. You start with your secret prime numbers inside the bag. To find the next special number, you reach in and pull out the smallest one you can find. Once you take that number out, you use it to grow some new, bigger numbers by multiplying it by each of your secret primes and putting those back into the bag. Because you keep pulling out the smallest ones first, you are always finding the next tiniest number in the sequence. You keep doing this over and over again, like picking the smallest marble out of a pile, until you have reached the spot you were looking for. When the pile has been shuffled and grown many times, the one left at the very front is exactly what you need.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Java	Python				TS
	WalkCCC	C++			Java	Python
	leetcode.ca	C++			Java	Python			Go
	LeetcodeHelp	C++			Java	Python
	MemoryLimitExceeded	C++				Python
	Progiez	C++			Java	Python
github	aylei		Rust
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	fengvyi	C++
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lennylxx							C
	linouk23	C++
	lkwq007					Python
	MacJim	C++
	ruoru		Rust
	suxrobGM						C#
	varunu28				Java
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality