Super Ugly Number

                                            
import heapq

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        ugly = [1]
        heap = [(p, 0, p) for p in primes]
        heapq.heapify(heap)
        
        while len(ugly) < n:
            val, idx, prime = heapq.heappop(heap)
            if val > ugly[-1]:
                ugly.append(val)
            heapq.heappush(heap, (prime * ugly[idx], idx + 1, prime))
        
        return ugly[-1]

                                            
int nthSuperUglyNumber(int n, int* primes, int primesSize) {
    int ugly[n];
    int index[primesSize];
    int factors[primesSize];
    
    ugly[0] = 1;
    
    for (int i = 0; i < primesSize; i++) {
        index[i] = 0;
        factors[i] = primes[i];
    }
    
    for (int i = 1; i < n; i++) {
        int min_val = __INT_MAX__;
        
        for (int j = 0; j < primesSize; j++) {
            min_val = factors[j] < min_val ? factors[j] : min_val;
        }
        
        ugly[i] = min_val;
        
        for (int j = 0; j < primesSize; j++) {
            if (min_val == factors[j]) {
                index[j]++;
                if (ugly[index[j]] <= INT_MAX / primes[j]) {
                    factors[j] = ugly[index[j]] * primes[j];
                } else {
                    factors[j] = INT_MAX;
                }
            }
        }
    }
    
    return ugly[n - 1];
}

                                            
var nthSuperUglyNumber = function(n, primes) {
    let ugly = new Array(n).fill(0);
    ugly[0] = 1;
    
    let pointer = new Array(primes.length).fill(0);
    
    for (let i = 1; i < n; i++) {
        ugly[i] = Number.MAX_VALUE;
        for (let j = 0; j < primes.length; j++) {
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[pointer[j]]);
        }
        
        for (let j = 0; j < primes.length; j++) {
            if (ugly[i] === primes[j] * ugly[pointer[j]]) {
                pointer[j]++;
            }
        }
    }
    
    return ugly[n - 1];
};

                                            
function nthSuperUglyNumber(n: number, primes: number[]): number {
    const dp = new Array(n).fill(0);
    dp[0] = 1;
    
    const indices = new Array(primes.length).fill(0);
    
    for (let i = 1; i < n; i++) {
        let min = Number.MAX_VALUE;
        
        for (let j = 0; j < primes.length; j++) {
            min = Math.min(min, dp[indices[j]] * primes[j]);
        }
        
        dp[i] = min;
        
        for (let j = 0; j < primes.length; j++) {
            if (min === dp[indices[j]] * primes[j]) {
                indices[j]++;
            }
        }
    }
    
    return dp[n - 1];
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @param Integer[] $primes
     * @return Integer
     */
    function nthSuperUglyNumber($n, $primes) {
        $ugly = [1];
        $idx = array_fill(0, count($primes), 0);
        
        while (count($ugly) < $n) {
            $next = PHP_INT_MAX;
            for ($i = 0; $i < count($primes); $i++) {
                $next = min($next, $ugly[$idx[$i]] * $primes[$i]);
            }
            $ugly[] = $next;
            
            for ($i = 0; $i < count($primes); $i++) {
                if ($ugly[$idx[$i]] * $primes[$i] == $next) {
                    $idx[$i]++;
                }
            }
        }
        
        return $ugly[$n - 1];
    }
}

                                            
class Solution {
    func nthSuperUglyNumber(_ n: Int, _ primes: [Int]) -> Int {
        var ugly = [1]
        var index = Array(repeating: 0, count: primes.count)

        while ugly.count < n {
            var next = Int.max
            for i in 0..<primes.count {
                next = min(next, primes[i] * ugly[index[i]])
            }

            for i in 0..<primes.count {
                if next == primes[i] * ugly[index[i]] {
                    index[i] += 1
                }
            }

            ugly.append(next)
        }

        return ugly.last ?? 1
    }
}

                                            
class Solution {
  int nthSuperUglyNumber(int n, List<int> primes) {
    List<int> ugly = List.filled(n, 0);
    ugly[0] = 1;
    
    List<int> indexes = List.filled(primes.length, 0);
    
    for (int i = 1; i < n; i++) {
      int min = primes[0] * ugly[indexes[0]];
      for (int j = 1; j < primes.length; j++) {
        min = min < primes[j] * ugly[indexes[j]] ? min : primes[j] * ugly[indexes[j]];
      }
      
      ugly[i] = min;
      
      for (int j = 0; j < primes.length; j++) {
        if (min == primes[j] * ugly[indexes[j]]) {
          indexes[j]++;
        }
      }
    }
    
    return ugly[n - 1];
  }
}

                                            
func nthSuperUglyNumber(n int, primes []int) int {
    if n == 1 {
        return 1
    }

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

    ptrs := make([]int, len(primes))

    for i := 1; i < n; i++ {
        ugly[i] = primes[0] * ugly[ptrs[0]]
        for j := 1; j < len(primes); j++ {
            ugly[i] = min(ugly[i], primes[j]*ugly[ptrs[j]])
        }
        for j := 0; j < len(primes); j++ {
            if ugly[i] == primes[j]*ugly[ptrs[j]] {
                ptrs[j]++
            }
        }
    }

    return ugly[n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer} n
# @param {Integer[]} primes
# @return {Integer}
def nth_super_ugly_number(n, primes)
    ugly = [1]
    pointer = Array.new(primes.length, 0)
    
    while ugly.length < n
        candidates = primes.map.with_index { |prime, i| ugly[pointer[i]] * prime }
        min_val = candidates.min
        
        candidates.each_with_index do |candidate, i|
            pointer[i] += 1 if candidate == min_val
        end
        
        ugly << min_val
    end
    
    return ugly.last
end

To solve this coding challenge, we'll use the concept of dynamic programming along with a min-heap to efficiently find the nth super ugly number. The key lies in leveraging the properties of prime factors and maintaining a sorted list of super ugly numbers.

Step-by-Step Explanation

Explanation

Initialization :

Start by initializing an array called
ugly

that will store all super ugly numbers in order. The first super ugly number is always
1

because it's the multiplication base.
A min-heap,
heap

, will store elements in the form of tuples:
(current_value, index_in_ugly, prime)

. Each tuple represents the next potential super ugly number generated by multiplying a
prime

with a value from the
ugly

list at position
index_in_ugly

.

Heap Initialization :

Populate the heap with initial tuples for each prime in the input list. Each tuple will start with the prime itself, as
1 * prime

.

Generating Super Ugly Numbers :

Use a while loop to continually pop the smallest item from the heap. This ensures that we always get the next smallest super ugly number.
If the popped number is greater than the last number in the
ugly

array, append it to
ugly

to ensure no duplicates.
Push the next potential value (which is the current prime multiplied by the next value in
ugly

) back into the heap.

Termination :

Continue this process until we have
n

ugly numbers in the
ugly

array. The last added number will be our answer.

Detailed Steps in Pseudocode

                                            
# Initialize array to store super ugly numbers
ugly = [1]

# Initialize heap with initial primes
heap = []
for prime in primes:
    # Push a tuple (prime, 0, prime) indicating the initial value of the prime, 
    # the index in the ugly list, and the prime itself
    push heap (prime, 0, prime)

# While loop to find first n super ugly numbers
while length of ugly < n:
    # Extract the minimum element from the heap
    (current_value, index_in_ugly, prime) = pop heap
    
    # If the smallest value is greater than the last added in the ugly list,
    # it is a new super ugly number, add it 
    if current_value > last element in ugly:
        append current_value to ugly
        
    # Calculate the next value for the current prime by advancing the index
    next_value = prime * ugly[index_in_ugly + 1]
    
    # Push the next tuple back to heap
    push heap (next_value, index_in_ugly + 1, prime)

# The nth super ugly number is the last value in the ugly array
return last element of ugly

Breakdown of Key Parts:

Initialization :

Here
ugly

array starts with
[1]

.
The heap will initially store tuples for each prime
(prime, 0, prime)

where
0

indicates the starting index for multiplications.

Heap Operations :

The
heapq

module helps maintain a min-heap in Python, but here we're using a generic min-heap concept.
heapq.heappop(heap)

equivalent is
pop heap

which removes and returns the smallest element.
heapq.heappush(heap, tuple)

equivalent is
push heap tuple

adding a new potential value to the heap.

While Loop :

Continues to fetch the smallest possible super ugly number not yet included.
Ensure to push tuples back into the heap only after multiplying with the respective prime and advancing the position.

This structured approach ensures efficient computation for large values of

n

and multiple primes. Remember, even though the pseudocode provided is language-agnostic, the core logic and steps remain consistent regardless of the programming environment.