TLE in Ruby - Why?


  • 0
    D

    It seems I've followed pretty much both the optimization and the algorithm given in the link... Not sure what more can I do.

    require 'set'
    
    def numbers_with_multiples_less_than n
      (2...(Math.sqrt(n)).ceil)
    end
    
    def primes_till n
      possible_primes = Set.new(2...n)
    
      (numbers_with_multiples_less_than n).each do |i|
        if possible_primes.include? i
          possible_primes = possible_primes - Set.new(multiples i**2,i,n)
        end
      end
    
      possible_primes
    end
    
    def multiples start,step_size,max
      (start...max).step(step_size)
    end
    
    
    # @param {Integer} n
    # @return {Integer}
    def count_primes(n)
       primes_till(n).count
    end

  • 0
    E

    IMO, subtraction between sets could be really time consuming. In Ruby, Set is internally implemented by Hash, so it's slower than Hash. For both Hash and Set, deleting objects could not be considered as constant time process.

    You can try to use array or hash table instead for this problem.


Log in to reply
 

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