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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/**
 * Dynamic Programming with Multiple Pointers
 * Time Complexity: O(n * k) - We need to fill n elements in the ugly array, and for each element, we consider k prime numbers
 * 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
 * 
 * @param {number} n - The position in the sequence to find
 * @param {number[]} primes - Array of prime numbers
 * @return {number} - The nth super ugly number
 */
function nthSuperUglyNumberDP(n, primes) {
  // Initialize the ugly array with the first super ugly number
  const ugly = new Array(n);
  ugly[0] = 1;
  
  // Initialize pointers for each prime
  const pointers = new Array(primes.length).fill(0);
  
  // Generate the remaining super ugly numbers
  for (let i = 1; i < n; i++) {
    // Find the next super ugly number
    let nextUgly = Infinity;
    for (let j = 0; j < primes.length; j++) {
      const candidate = ugly[pointers[j]] * primes[j];
      nextUgly = Math.min(nextUgly, candidate);
    }
    
    // Set the next super ugly number
    ugly[i] = nextUgly;
    
    // Update pointers
    for (let j = 0; j < primes.length; j++) {
      if (ugly[pointers[j]] * primes[j] === nextUgly) {
        pointers[j]++;
      }
    }
  }
  
  return ugly[n - 1];
}
 
/**
 * Priority Queue (Min Heap) Approach
 * 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
 * Space Complexity: O(n * k) - The priority queue and the set can contain up to n * k elements in the worst case
 * 
 * @param {number} n - The position in the sequence to find
 * @param {number[]} primes - Array of prime numbers
 * @return {number} - The nth super ugly number
 */
function nthSuperUglyNumber(n, primes) {
  // Simple MinHeap implementation
  class MinHeap {
    constructor() {
      this.heap = [];
    }
    
    push(val) {
      this.heap.push(val);
      this.bubbleUp(this.heap.length - 1);
    }
    
    pop() {
      if (this.heap.length === 0) return null;
      const min = this.heap[0];
      const last = this.heap.pop();
      if (this.heap.length > 0) {
        this.heap[0] = last;
        this.bubbleDown(0);
      }
      return min;
    }
    
    bubbleUp(index) {
      while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex] <= this.heap[index]) break;
        [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
        index = parentIndex;
      }
    }
    
    bubbleDown(index) {
      const lastIndex = this.heap.length - 1;
      while (true) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let smallestIndex = index;
        
        if (leftChildIndex <= lastIndex && this.heap[leftChildIndex] < this.heap[smallestIndex]) {
          smallestIndex = leftChildIndex;
        }
        if (rightChildIndex <= lastIndex && this.heap[rightChildIndex] < this.heap[smallestIndex]) {
          smallestIndex = rightChildIndex;
        }
        
        if (smallestIndex === index) break;
        [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
        index = smallestIndex;
      }
    }
    
    size() {
      return this.heap.length;
    }
  }
  
  // Initialize priority queue and set
  const pq = new MinHeap();
  const seen = new Set();
  
  // Add the first super ugly number
  pq.push(1);
  seen.add(1);
  
  // Find the nth super ugly number
  let x = 0;
  for (let i = 0; i < n; i++) {
    x = pq.pop();
    
    for (const p of primes) {
      const product = x * p;
      
      // Check for integer overflow and duplicates
      if (product <= 2147483647 && !seen.has(product)) {
        pq.push(product);
        seen.add(product);
      }
      
      // Optimization to avoid duplicates
      if (x % p === 0) {
        break;
      }
    }
  }
  
  return x;
}
 
// Test cases
console.log(nthSuperUglyNumber(12, [2, 7, 13, 19])); // 32
console.log(nthSuperUglyNumber(1, [2, 3, 5])); // 1