#313

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Super Ugly Number

Compute the nth super ugly number efficiently using dynamic programming with state transitions based on the given prime factors array.

array math dynamic programming

Problem Statement

A super ugly number is defined as a positive integer whose prime factors are all contained within a given array primes. Given an integer n and an array primes, your task is to determine the nth super ugly number in ascending order.

The first super ugly number is always 1, which has no prime factors. Subsequent super ugly numbers are generated by multiplying previous numbers by any prime in the primes array. You must return the nth super ugly number, guaranteed to fit within a 32-bit signed integer.

Examples

Example 1

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

Output: 32

[1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2

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

Output: 1

1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints

1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.

Solution Approach

Use dynamic programming array to store results

Initialize an array dp of size n where dp[i] represents the ith super ugly number. Start with dp[0] = 1. The array will store computed super ugly numbers in ascending order, ensuring no duplicates or missing numbers.

Maintain pointers for each prime factor

For each prime in primes, maintain a pointer indicating which dp element it should multiply next. This allows you to efficiently generate the next candidate numbers by multiplying the prime with its corresponding pointer value, tracking the minimal next super ugly number across all primes.

Iteratively build sequence using state transitions

At each step, select the minimum candidate from all prime-pointer products and append it to dp. Advance the pointers for all primes that generated this minimum value. Repeat until dp[n-1] is filled. This state transition ensures correct ordering and avoids recomputation or missing numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * k) where n is the target index and k is the number of primes, since each step examines k candidates. Space complexity is O(n + k) to store the dp array and pointers, which is efficient for n up to 10^5 and primes up to 100.

What Interviewers Usually Probe

Asks about efficiency beyond brute force multiplication
Mentions handling large n with multiple primes
Checks understanding of state transition dynamic programming

Common Pitfalls or Variants

Common pitfalls

Failing to initialize dp[0] as 1
Forgetting to advance multiple pointers when duplicate minimum occurs
Using naive brute-force multiplication, leading to timeouts for large n

Follow-up variants

Compute the nth ugly number with fixed primes [2,3,5] instead of a given array
Find all super ugly numbers less than a given limit instead of nth number
Count the number of super ugly numbers within a range [L, R]

FAQ

What is the key idea behind generating super ugly numbers?

The key idea is using state transition dynamic programming where each number is derived by multiplying previous numbers by allowed primes and selecting the minimal next candidate.

Can duplicates occur in the sequence of super ugly numbers?

Yes, duplicates can occur if multiple primes multiply to the same candidate number; you must advance all corresponding pointers to avoid repeating numbers.

What should I initialize as the first super ugly number?

The first super ugly number is always 1, representing the base of the sequence with no prime factors.

How does pointer management improve efficiency?

Maintaining a pointer for each prime ensures you only multiply each prime with the smallest unused dp value, avoiding redundant calculations and reducing overall complexity.

Why is this problem considered a state transition dynamic programming pattern?

Because each super ugly number depends on previous numbers and pointers, forming a deterministic state that transitions to the next number based on minimal candidate selection across primes.

terminal

Solution

Solution 1: Priority Queue (Min Heap)

We use a priority queue (min heap) to maintain all possible super ugly numbers, initially putting $1$ into the queue.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        q = [1]
        x = 0
        mx = (1 << 31) - 1
        for _ in range(n):
            x = heappop(q)
            for k in primes:
                if x <= mx // k:
                    heappush(q, k * x)
                if x % k == 0:
                    break
        return x

Solution 2

#### Go

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        q = [1]
        x = 0
        mx = (1 << 31) - 1
        for _ in range(n):
            x = heappop(q)
            for k in primes:
                if x <= mx // k:
                    heappush(q, k * x)
                if x % k == 0:
                    break
        return x

Continue Practicing

#368 largest divisible subset #396 rotate function #486 predict the winner