As this is an extension of problem 264. Ugly Number II, we could just generalise from it.

While, in my opinion, the hard (weird) part is that I've got several TLEs.

#### Plain O(nk) solution

TLE version

```
# Plain O(n*k)
def nth_super_ugly_number(n, primes)
numbers = [1]
# TLE by this (expensive) hash
primes_and_ids = primes.reduce({}){|ha, prime| ha[prime] = 0; ha }
(n-1).times do
candidates = primes_and_ids.map{|prime, id| [ prime, prime * numbers[id] ]}
min = candidates.map(&:last).min
candidates.each do |prime, candidate|
next unless candidate == min
primes_and_ids[prime] += 1
end
numbers << min
end
numbers[n-1]
end
```

I used a hash above, which might be a little expensive with massive inputs. So I replaced it with an array. Got passed.

```
# Plain O(n*k)
def nth_super_ugly_number(n, primes)
numbers = [1]
idx = [0]*primes.count
(n-1).times do
min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min
primes.each_with_index do |prime, i|
next unless min == prime * numbers[ idx[i] ]
idx[i] += 1
end
numbers << min
end
numbers[n-1]
end
```

#### Heap Solution (TLE)

Using a Priority Queue (a minimum heap) aims to improves this linear searching code:

```
min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min
```

While, just as vcoderld said in Java three methods, 23ms, 36 ms, 58ms(with heap), performance explained

Besides, the remain part (the inner loop) takes complexity between Nlog(K) and NKlog(K), i.e for the best case there is only one peek == next, it takes log(K), and for the worst case, all objects in the heap == next, so it takes Klog(K). So this loop is not necessarily < KN. That's why the heap solution is slower than the KN solution.

It's true to take `O(nklogk)`

in the worst case, when all elements have equal keys in heap (delete then insert). But I'm doubted of the test cases. Ok, leave my TLE minimum heap code as a note

```
class PriorityQueue
attr_accessor :array, :n, :comparison
def initialize(arr = [], &comparison)
@n = arr.length
@array = arr
@array.unshift nil
@comparison = comparison || ->(a,b){ a < b }
build
end
def insert(node)
self.n += 1
array[n] = node
swim(array, n, n)
end
def delete_min
return nil if n < 1
min = array[1]
swap(array, 1, n)
self.n -= 1
sink(array, 1, n)
return min
end
def get_min
return nil if n < 1
array[1]
end
def size
n
end
private
def build
(n/2).downto(1) do |k|
sink(array, k, n)
end
end
def swap(array, i, j)
t = array[i]; array[i] = array[j]; array[j] = t
end
def sink(array, k, n)
while 2*k <= n
j = 2*k
j += 1 if j+1 <= n && less(j+1, j)
break if !less(j, k)
swap(array, j, k)
k = j
end
end
def swim(array, k, n)
while k/2 >= 1
j = k/2
break if !less(k, j)
swap(array, j, k)
k = j
end
end
def less(i, j)
comparison[ array[i], array[j] ]
end
end
# Use Priority Queue O(n*logk)
def nth_super_ugly_number(n, primes)
numbers = [1]
idx = [0]*primes.count
pair = Struct.new(:key, :value)
candidates = primes.map do |prime|
key = prime # prime*numbers[0]
value = prime
pair.new(key, value)
end
# Minimum heap
heapq = PriorityQueue.new(candidates){|a,b| a.key < b.key}
(n-1).times do
min = heapq.get_min.key
numbers << min
while min == heapq.get_min.key
min_pair = heapq.delete_min
prime = min_pair.value
i = primes.index(prime)
idx[i] += 1
new_pair = pair.new( prime * numbers[ idx[i] ], prime )
heapq.insert(new_pair)
end
end
numbers[n-1]
end
```