# Is the time limit too strict for Ruby?

• First I tried a solution based on Ugly Number II, but got TLE.

``````def nth_super_ugly_number(n, primes)
nums = Array.new(n, 1)
qs, is = Array.new(primes.size, 1), Array.new(primes.size, 0)

1.upto(n - 1) do |i|
primes.each_with_index { |prime, idx| qs[idx] = nums[is[idx]] * prime }
nums[i] = qs.min
is.each_with_index { |_, idx| is[idx] += 1 if qs[idx] == nums[i] }
end

nums[n - 1]
end
``````

Then I tryied to solve it using a priority queue, but still got LTE. (Note Ruby has no built-in priority queue, you have to implement it yourself)

``````class PriorityQueue
def initialize(cmp)
@queue, @cmp = [], cmp
end

def <<(value)
@queue << value; _swim_(@queue.size - 1); self
end

def shift
@queue[0], @queue[-1] = @queue[-1], @queue[0]
@queue.pop.tap { _sink_(0) }
end

def peek
@queue[0]
end

def empty?
@queue.empty?
end

private def _swim_(k)
while k > 0 && @cmp.call(@queue[k], @queue[(k - 1) / 2])
@queue[k], @queue[(k - 1) / 2] = @queue[(k - 1) / 2], @queue[k]
k = (k - 1) / 2
end
end

private def _sink_(k)
while k * 2 + 1 < @queue.size
kk  = k * 2 + 1
kk += 1 if @queue[kk + 1] && @cmp.call(@queue[kk + 1], @queue[kk])
break if @cmp.call(@queue[k], @queue[kk])

@queue[k], @queue[kk] = @queue[kk], @queue[k]
k = kk
end
end
end

# @param {Integer} n
# @param {Integer[]} primes
# @return {Integer}
def nth_super_ugly_number(n, primes)
nums = Array.new(n, 1)
minpq = PriorityQueue.new(Proc.new{ |(_, _, n1), (_, _, n2)| n1 < n2 })

primes.each_with_index do |prime, index|
minpq << [index, prime, prime]
end

1.upto(n - 1) do |i|
nums[i] = minpq.peek[2]

loop do
index, prime, _ = minpq.shift
minpq << [index + 1, prime, nums[index] * prime]
break if minpq.empty? || minpq.peek[2] != nums[i]
end
end

nums[n - 1]
end
``````

I did some tricks to speed up, but failed. Any suggestion?

• We don't have access to your submission pages. Please include your code right in your question.

• I added the original code.

• The administrator relexed the time limitation or we got a better VM, no matter how the problem resolved.

One solution based on Ugly Number II cost 1700ms. Another solution based on priority queue still got TLE, but we could do some tricks to speed up though it's much unreadable, The code below cost 1900ms:

``````class PriorityQueue
def initialize
@queue = [1]
end

def <<(value)
@queue << value; _swim_(@queue.size - 1); self
end

def shift
@queue[1], @queue[-1] = @queue[-1], @queue[1]
@queue.pop.tap { _sink_(1) }
end

def peek
@queue[1]
end

def empty?
@queue.size == 1
end

private def _swim_(k)
while k > 1 && @queue[k][2] < @queue[k / 2][2]
@queue[k], @queue[k / 2] = @queue[k / 2], @queue[k]
k = k / 2
end
end

private def _sink_(k)
while k * 2 < @queue.size
kk  = k * 2
kk += 1 if @queue[kk + 1] && @queue[kk + 1][2] < @queue[kk][2]
break if @queue[k][2] < @queue[kk][2]

@queue[k], @queue[kk] = @queue[kk], @queue[k]
k = kk
end
end
end

def nth_super_ugly_number(n, primes)
nums = Array.new(n, 1)
minpq = PriorityQueue.new

primes.each_with_index do |prime, index|
minpq << [index, prime, prime]
end

1.upto(n - 1) do |i|
nums[i] = minpq.peek[2]

loop do
index, prime, _ = minpq.shift
minpq << [index + 1, prime, nums[index] * prime]
break if minpq.empty? || minpq.peek[2] != nums[i]
end
end

nums[n - 1]
end``````

• @skv46851 @StefanPochmann It'd be great if OJ had a pre-installed gem for Priority Queues. Many questions such as https://leetcode.com/problems/merge-k-sorted-lists/#/solutions require PQ and ruby doesn't have a standard library for that.
The gem https://github.com/rubyworks/pqueue is pretty popular for PQ in Ruby and has the basic methods for PQ. Is it possible to add it to all VMs running Ruby so it can be accessed using a simple

require 'pqueue'

• @evidanary That question doesn't require PQ. You can just collect all values in an array, sort it, and turn it into a list. If you do want to write a solution using PQ, you could also just use another language.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.