Solution: Super Ugly Number

Explore how to find the nth super ugly number efficiently by using a k-way merge approach combined with a min heap. Understand how to dynamically generate numbers based on given prime factors, avoid duplicates, and manage computations in ascending order. This lesson guides you through implementing the algorithm with optimal time and space complexity, helping you master problem-solving techniques involving heaps and prime factors.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

Given an integer n and an array of distinct prime numbers primes, return the n-th super ugly number. A super ugly number is a positive integer whose only prime factors are from a given array primes.

The n-th super ugly number is guaranteed to fit within a 32-bit signed integer.

Constraints:

$1 \leq$ n $\leq 10^5$
$1 \leq$ primes.length $\leq 100$
$2 \leq$ primes[i] $\leq 1000$
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in an ascending order.

Solution

The problem is solved using a k-way merge approach combined with a min heap, ensuring that numbers are generated in strictly increasing order while avoiding redundancy. Instead of precomputing all possible multiples of the given prime factors, we dynamically construct the list by continuously tracking and merging only the smallest valid values at each step. This prevents unnecessary computations and avoids storing large sets of numbers in advance.

The algorithm begins with a list containing only $1$ and a min heap initialized with the first multiple of each prime, which is the prime itself. At each step, the smallest number is extracted from the heap and added to the list if it has not already been included. The extracted prime is multiplied by the next number in the list that comes after the last number used for this prime to generate the next number. The newly computed number is then pushed back into the heap, allowing the process to continue in an ordered manner. This process continues until the desired count is reached.

The steps of the algorithm are as follows:

Create an array, ugly, and initialize it with 1, as 1 is always the first super ugly number.
Create a minHeap and push the first multiple of each prime (which is the prime itself) into the heap as (prime, prime, 0), where:
1. The first value represents the next potential ugly number.
2. The second value keeps track of the prime factor that generated the next potential ugly number.
3. The third value is the index of the ugly number multiplied by the prime to generate the potential ugly number. It helps us track which ugly number was last multiplied by the prime to correctly compute the next multiple.
Iterate until n super ugly numbers are found:
1. Extract the smallest number (nextUgly) from the heap. We also extract the corresponding prime and index from the heap.
2. If nextUgly is not a duplicate (since multiple primes can generate the same number), append it to ugly.
3. Compute the next multiple (number) by multiplying the extracted prime and the next number in ugly that comes after the last number used for this prime.
4. Push the new tuple (prime * ugly[index + 1], prime, index + 1) back into the heap.
The n-th super ugly number is the last element in the ugly list. Return this value as the final result.

Let’s look at the following illustration to get a better understanding of the solution:

Solution

Commented Solution

/* The following definition is for MinHeap.
  You can use the same methods for MaxHeap.
  class MinHeap {
    size();          // return number of elements
    peek();          // return top element without removing
    push(val);       // insert element
    pop();           // remove and return top element
  }
*/
function nthSuperUglyNumber(n, primes) {
    let ugly = [1];  
    let minHeap = new MinHeap(); 
    for (let prime of primes) {
        minHeap.push([prime, prime, 0]);
    }
    while (ugly.length < n) {
        let [nextUgly, prime, index] = minHeap.pop();
        if (nextUgly !== ugly[ugly.length - 1]) {
            ugly.push(nextUgly);
        }
        minHeap.push([prime * ugly[index + 1], prime, index + 1]);
    }
    return ugly[n - 1]; 
}
export {nthSuperUglyNumber};
// Test cases
const nValues = [12, 1, 15, 10, 8];
const primesList = [
    [2, 7, 13, 19],
    [2, 3, 5],
    [3, 5, 7],
    [2, 5, 11],
    [3, 11, 17]
];
for (let i = 0; i < nValues.length; i++) {
    console.log(i+1+ ".\tn:", nValues[i]);
    console.log(`\tprimes: [${primesList[i].join(", ")}]`);
    let result = nthSuperUglyNumber(nValues[i], primesList[i]);
    console.log(`\n\t${nValues[i]}th super ugly number is ${result}`);
    console.log("-".repeat(100));
}

Super Ugly Number

Solution: Super Ugly Number

Statement

Solution

Time complexity

Space complexity