101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming with Multiple Pointers - Complex approach
  2. Priority Queue (Min Heap) Approach - Complex approach

Approach 1: Dynamic Programming with Multiple Pointers

Let's start by understanding how to generate the sequence of super ugly numbers. We know that:

  • The first super ugly number is always 1
  • Each subsequent super ugly number is formed by multiplying an existing super ugly number by one of the prime factors

Thinking Process: We can use dynamic programming to build the sequence. Let's define an array ugly where ugly[i] represents the ith super ugly number. We initialize ugly[0] = 1.

To find the next super ugly number, we need to consider all possible candidates. For each prime number p in the primes array, we maintain a pointer ptr[p] that points to the index in the ugly array. The candidate from this prime would be ugly[ptr[p]] * p.

The next super ugly number is the minimum of all these candidates. After we find it, we increment the pointers for all primes that contributed to this minimum value.

Intuition: This approach ensures that we generate the super ugly numbers in ascending order, and we don't miss any number in the sequence.

Algorithm:

  1. Initialize an array ugly of size n with ugly[0] = 1.
  2. Initialize an array pointers of size primes.length, all set to 0.
  3. For i from 1 to n-1:
  4. a. Initialize nextUgly = infinity.
  5. b. For each prime p in primes:
  6. i. Calculate candidate = ugly[pointers[p]] * p.
  7. ii. Update nextUgly = min(nextUgly, candidate).
  8. c. Set ugly[i] = nextUgly.
  9. d. For each prime p in primes:
  10. i. If ugly[pointers[p]] * p == nextUgly, increment pointers[p].
  11. Return ugly[n-1].

Time Complexity:

O(n * k)

We need to fill n elements in the ugly array, and for each element, we consider k prime numbers, where k is the length of the primes array.

Space Complexity:

O(n + k)

We use an array of size n to store the ugly numbers and an array of size k to store the pointers.

Approach 2: Priority Queue (Min Heap) Approach

Another approach is to use a priority queue (min heap) to efficiently find the next super ugly number.

Thinking Process: We start by pushing 1 into the priority queue. Then, in each iteration, we pop the smallest element from the queue (which is the next super ugly number), multiply it by each prime in the primes array, and push the products back into the queue.

However, this approach can lead to duplicate numbers in the queue. To avoid this, we can use a set to keep track of numbers we've already seen, or we can use a more efficient approach: for each super ugly number x, we only consider multiplying it by primes p such that x is divisible by a prime less than or equal to p.

Intuition: The priority queue ensures that we always pick the smallest candidate as the next super ugly number, and the optimization helps us avoid generating duplicate numbers.

Algorithm:

  1. Initialize a priority queue (min heap) and push 1 into it.
  2. Initialize a set to keep track of numbers we've already seen, and add 1 to it.
  3. For i from 1 to n:
  4. a. Pop the smallest element x from the queue.
  5. b. If i == n, return x.
  6. c. For each prime p in primes:
  7. i. Calculate product = x * p.
  8. ii. If product is not in the set:
  9. 1. Push product into the queue.
  10. 2. Add product to the set.
  11. iii. If x % p == 0, break (optimization to avoid duplicates).

Time Complexity:

O(n * k * log(n * k))

We perform n extractions from the priority queue, and for each extraction, we potentially add k new elements. Each operation on the priority queue takes log(queue size) time, and the queue can grow to size n * k in the worst case.

Space Complexity:

O(n * k)

The priority queue and the set can contain up to n * k elements in the worst case.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function nthSuperUglyNumber(n, primes):
    // Initialize the ugly array with the first super ugly number
    ugly = new array of size n
    ugly[0] = 1
    
    // Initialize pointers for each prime
    pointers = new array of size primes.length, all set to 0
    
    // Generate the remaining super ugly numbers
    for i from 1 to n-1:
        // Find the next super ugly number
        nextUgly = infinity
        for j from 0 to primes.length-1:
            candidate = ugly[pointers[j]] * primes[j]
            nextUgly = min(nextUgly, candidate)
        
        // Set the next super ugly number
        ugly[i] = nextUgly
        
        // Update pointers
        for j from 0 to primes.length-1:
            if ugly[pointers[j]] * primes[j] == nextUgly:
                pointers[j]++
    
    return ugly[n-1]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone