Currently I stumbled upon a question that appeared easy, so I solved it. The problem came afterwards as the solution passed the visible tests(6856ms), but upon clicking a final submit button where my solution was further tested on hidden and quite possibly more complex tests, I get a time out error. The catch here is my solution should satisfy all the hidden tests in under 7000ms or I will receive the time out error. I tried vigorously to optimize the solution, but with no luck. I am not looking for an answer, but a hint on making the algo faster would be helpful.
The object of the problem was: Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!
Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.
The result will be an array of arrays, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.
My code and the time of execution of the 3 visible tests are as follows:
def list_squared(m, n)
p (m..n).map{|num| [num, (1..num).map{|number| number ** 2 if num % number == 0}.compact.inject(:+)]}.collect{|num, sum| [num, sum] if (1..sum).any?{|nums| nums ** 2 == sum}}.compact
end
beginning_time = Time.now
list_squared(1, 250)# [[1, 1], [42, 2500], [246, 84100]])
list_squared(42, 250)# [[42, 2500], [246, 84100]])
list_squared(250, 500)# [[287, 84100]])
end_time = Time.now
puts "Time elapsed #{(end_time - beginning_time)*1000} milliseconds" #Time elapsed 7734.796764000001 milliseconds
Thanks for reading.
