LeetCode Problem 313

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

LeetCode 313 - Super Ugly Number

Problem Understanding

This problem asks us to find the nth number in a special sequence called "super ugly numbers".

A super ugly number is a positive integer whose prime factors come only from the given array primes. That means every factorization of the number can use only primes from this list.

For example, if:

primes = [2,7,13,19]

then valid super ugly numbers include:

1, 2, 4, 7, 8, 13, 14, 16, ...

because each number can be formed using only the primes 2, 7, 13, and 19.

The number 1 is always considered a super ugly number because it has no prime factors.

The input consists of:

• n, the position in the sequence we want to find
• primes, the allowed prime factors

The output is the nth super ugly number.

The constraints are important:

• n can be as large as 100000
• primes.length can be up to 100
• Each prime is at most 1000

These constraints immediately tell us that generating numbers naively and checking factorization repeatedly would be far too slow. We need a dynamic programming style solution that builds the sequence efficiently.

There are several important edge cases:

• n = 1, where the answer must always be 1

• Multiple primes may generate the same next number, such as:

• 2 * 7 = 14

• 7 * 2 = 14

If duplicates are not handled carefully, the sequence will contain repeated values.

• Large values of n require an efficient algorithm with near linear complexity.
• The primes array may contain many values, so repeatedly scanning or recomputing expensive operations can become costly.

The problem guarantees:

• All primes are unique
• The primes array is sorted
• The answer fits inside a 32-bit signed integer

These guarantees simplify implementation details.

Approaches

Brute Force Approach

The most straightforward approach is to iterate through all positive integers and test whether each one is a super ugly number.

To test a number, we repeatedly divide it by every allowed prime. If the number can eventually be reduced to 1, then all its prime factors belong to the allowed set, so it is a super ugly number.

For example:

28
= 2 * 2 * 7

Since all factors belong to [2,7,13,19], it is valid.

However, this approach becomes extremely inefficient for large n.

The sequence grows slowly compared to the number of integers we must check. Many numbers are rejected, and repeated factorization is expensive.

With n up to 100000, this brute force method is not practical.

Optimal Dynamic Programming Approach

The key insight is that every super ugly number comes from multiplying an earlier super ugly number by one of the allowed primes.

Suppose we already know the sequence:

1, 2, 4, 7, 8

Then future candidates can be generated by multiplying these numbers by each prime.

This is very similar to the classic "Ugly Number II" problem.

We maintain:

• A DP array storing generated super ugly numbers in sorted order
• One pointer per prime
• Each pointer tracks which DP value should next be multiplied by that prime

For every iteration:

1. Compute all candidate values
2. Choose the minimum candidate
3. Add it to the sequence
4. Advance every pointer that produced this minimum

Advancing all matching pointers is critical for avoiding duplicates.

This approach generates numbers directly in sorted order without checking irrelevant integers.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Extremely large, impractical	O(1)	Checks every integer and factorizes repeatedly
Optimal Dynamic Programming	O(n * k)	O(n + k)	Efficiently generates only valid super ugly numbers

Here, k = len(primes).

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Create a DP array called ugly of size n.

The array will store the first n super ugly numbers in sorted order.

Initialize:

ugly[0] = 1

because 1 is always the first super ugly number. 2. Create a pointer array called indices.

Each prime gets one pointer.

indices[i]

tells us which position in ugly should currently be multiplied by primes[i].

Initially:

indices = [0, 0, 0, ...]

3. Create a candidate array.

For each prime:

candidates[i] = ugly[indices[i]] * primes[i]

These are the next possible super ugly numbers. 4. For each position from 1 to n - 1:

1. Find the minimum value among all candidates.
2. Append this minimum into the DP array.
3. For every prime whose candidate equals this minimum:

• Advance its pointer
• Recompute its candidate

5. Continue until the DP array contains n numbers.
6. Return:

ugly[n - 1]

Why it works

The algorithm works because every super ugly number can be expressed as:

(previous super ugly number) * (allowed prime)

The DP array always remains sorted because we repeatedly choose the smallest available candidate.

The pointer mechanism guarantees:

• Every valid number is eventually generated
• Numbers appear in increasing order
• Duplicate values are skipped correctly by advancing all matching pointers

This ensures the generated sequence is exactly the sequence of super ugly numbers.

Python Solution

from typing import List

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        k = len(primes)

        ugly = [1] * n
        indices = [0] * k
        candidates = primes[:]

        for i in range(1, n):
            next_ugly = min(candidates)
            ugly[i] = next_ugly

            for j in range(k):
                if candidates[j] == next_ugly:
                    indices[j] += 1
                    candidates[j] = ugly[indices[j]] * primes[j]

        return ugly[-1]

The implementation follows the dynamic programming approach directly.

The ugly array stores the generated sequence. It starts with 1.

The indices array tracks which DP value each prime should multiply next.

The candidates array stores the current next possible value for each prime.

At every iteration:

• We choose the smallest candidate
• Store it into the sequence
• Advance every matching pointer

The duplicate handling is especially important. Consider:

2 * 7 = 14
7 * 2 = 14

If only one pointer advanced, 14 would appear multiple times. Advancing all matching pointers prevents duplicates.

The algorithm efficiently generates the sequence in sorted order without unnecessary factorization or validation.

Go Solution

func nthSuperUglyNumber(n int, primes []int) int {
	k := len(primes)

	ugly := make([]int, n)
	ugly[0] = 1

	indices := make([]int, k)
	candidates := make([]int, k)

	for i := 0; i < k; i++ {
		candidates[i] = primes[i]
	}

	for i := 1; i < n; i++ {
		nextUgly := candidates[0]

		for j := 1; j < k; j++ {
			if candidates[j] < nextUgly {
				nextUgly = candidates[j]
			}
		}

		ugly[i] = nextUgly

		for j := 0; j < k; j++ {
			if candidates[j] == nextUgly {
				indices[j]++
				candidates[j] = ugly[indices[j]] * primes[j]
			}
		}
	}

	return ugly[n-1]
}

The Go implementation mirrors the Python logic closely.

A few Go-specific details are worth noting:

• Slices are initialized using make
• We manually compute the minimum candidate because Go does not provide a built-in min for slices
• Integer overflow is not a concern because the problem guarantees the result fits in a 32-bit signed integer
• Arrays and slices are mutable, making pointer updates efficient

Worked Examples

Example 1

Input:
n = 12
primes = [2,7,13,19]

Initial state:

Variable	Value
ugly	[1]
indices	[0,0,0,0]
candidates	[2,7,13,19]

Iteration Trace

Iteration	Next Ugly	ugly Array	indices	candidates
1	2	[1,2]	[1,0,0,0]	[4,7,13,19]
2	4	[1,2,4]	[2,0,0,0]	[8,7,13,19]
3	7	[1,2,4,7]	[2,1,0,0]	[8,14,13,19]
4	8	[1,2,4,7,8]	[3,1,0,0]	[14,14,13,19]
5	13	[1,2,4,7,8,13]	[3,1,1,0]	[14,14,26,19]
6	14	[1,2,4,7,8,13,14]	[4,2,1,0]	[16,28,26,19]
7	16	[1,2,4,7,8,13,14,16]	[5,2,1,0]	[26,28,26,19]
8	19	[1,2,4,7,8,13,14,16,19]	[5,2,1,1]	[26,28,26,38]
9	26	[1,2,4,7,8,13,14,16,19,26]	[6,2,2,1]	[28,28,52,38]
10	28	[1,2,4,7,8,13,14,16,19,26,28]	[7,3,2,1]	[32,49,52,38]
11	32	[1,2,4,7,8,13,14,16,19,26,28,32]	[8,3,2,1]	[38,49,52,38]

Final answer:

32

Example 2

Input:
n = 1
primes = [2,3,5]

Initial state:

Variable	Value
ugly	[1]

Since n = 1, no iterations are needed.

Return:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * k)	Each iteration scans all primes
Space	O(n + k)	DP array plus pointer/candidate arrays

Here:

• n is the number of super ugly numbers generated
• k is the number of primes

For every generated number, we scan all k primes to:

• Find the minimum candidate
• Update matching candidates

Since k <= 100, this approach is efficient enough for n = 100000.

The DP array stores all generated numbers, requiring O(n) space.

Test Cases

sol = Solution()

# Provided examples
assert sol.nthSuperUglyNumber(12, [2, 7, 13, 19]) == 32  # standard example
assert sol.nthSuperUglyNumber(1, [2, 3, 5]) == 1  # smallest n

# Single prime
assert sol.nthSuperUglyNumber(5, [2]) == 16  # powers of 2

# Two primes
assert sol.nthSuperUglyNumber(10, [2, 3]) == 18  # mixed generation

# Duplicate generation handling
assert sol.nthSuperUglyNumber(7, [2, 7]) == 14  # 14 generated multiple ways

# Larger primes
assert sol.nthSuperUglyNumber(6, [29, 31]) == 841  # powers/combinations of large primes

# Many primes
assert sol.nthSuperUglyNumber(15, [2, 3, 5, 7, 11]) == 18  # multiple candidate sources

# Boundary style test
result = sol.nthSuperUglyNumber(100, [2, 3, 5])
assert result > 0  # verifies larger input execution

Test Summary

Test	Why
n=12, primes=[2,7,13,19]	Verifies standard example
n=1	Verifies smallest possible input
Single prime	Tests repeated multiplication of one value
Two primes	Tests interleaving candidate generation
Duplicate generation case	Ensures duplicates are removed correctly
Larger primes	Verifies handling of non-small factors
Many primes	Tests scaling with larger prime arrays
Larger n	Verifies performance characteristics

Edge Cases

Edge Case 1, n = 1

When n = 1, the correct answer is always 1.

This can easily cause bugs if the implementation assumes at least one iteration of sequence generation. Our implementation handles this naturally because the DP array starts with:

ugly[0] = 1

and the loop begins from index 1. Therefore, the function immediately returns 1.

Edge Case 2, Duplicate Candidate Generation

Multiple primes can produce the same value:

2 * 7 = 14
7 * 2 = 14

If only one pointer advances after generating 14, the next iteration would generate 14 again, causing duplicates in the sequence.

Our implementation avoids this by advancing every pointer whose candidate equals the chosen minimum.

This guarantees uniqueness.

Edge Case 3, Single Prime Array

If the primes array contains only one value:

primes = [2]

then the sequence becomes:

1, 2, 4, 8, 16, ...

Some implementations incorrectly assume multiple candidate sources exist.

Our implementation works correctly because the algorithm does not depend on the number of primes being greater than one. The single pointer simply advances each iteration.