Solution: Super Ugly Number

Discover how to solve the nth super ugly number problem by applying a k-way merge strategy combined with a min heap. Understand how to dynamically generate and track super ugly numbers using prime factors, optimizing for time and space complexity. This lesson reinforces practical coding techniques useful for coding interviews.

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