2
\$\begingroup\$

I am doing a problem my buddy gave to me and I have my solution which works but needs to be optimised. I have tried to optimise it as much as I can with my knowledge but it seems there is still room for improvement. I am trying to improve my ruby. Here is the challenge:

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.

 def list_squared(m, n)
   array = []
  (m..n).to_a.each do |i|
     q =  (1..i/2).to_a.push(i).map {|x| x**2 if i % x == 0 }.compact.reduce(:+)
     array << [i, q] if Math.sqrt(q) % 1 == 0
   end   
 array
end

This works but apparently is inefficient. Could someone point me in the right direction. I am assuming its the "map" but I initially had:

def list_squared(m, n)
 array = []
 (m..n).to_a.each do |i|
   q =  (1..i/2).to_a.select {|x| i % x == 0 }.push(i).map { |x| x**2 }.reduce(:+)
    array << [i, q] if Math.sqrt(q) % 1 == 0
  end   
 array
end
\$\endgroup\$
  • \$\begingroup\$ Consider (m..n).to_a.each. What happens if it evaluates to (0..1_000_000_000).to_a...? You've unnecessarily used a huge amount of memory where you could have iterated directly using each. \$\endgroup\$ – the Tin Man Oct 3 '16 at 16:00
  • \$\begingroup\$ Thanks Tin man. I made that change...its still taking over 8 secs to evaluate which is "considered" unacceptable by the challenge. I could look at the solutions but to do so, would mean I get no credit \$\endgroup\$ – GhostRider Oct 3 '16 at 16:02
  • \$\begingroup\$ What are you using for m and n? Just to have the same test case. \$\endgroup\$ – slowjack2k Oct 4 '16 at 10:57
  • \$\begingroup\$ That's a fair question that I should have explained. My code is put through a number of test cases (15) but I'm being told although it passes, my code is inefficient (too slow). \$\endgroup\$ – GhostRider Oct 4 '16 at 11:00
  • \$\begingroup\$ Sounds like a test from codility. \$\endgroup\$ – slowjack2k Oct 4 '16 at 11:14
2
\$\begingroup\$

You don't need to call to_a. Ranges are directly Enumerable.

Divisors always occur in pairs. You don't need to test (1..i/2); you only need to go up to \$\sqrt{i}\$.

For fast performance, though, you would need a solution based on number theory rather than brute-force enumeration.

\$\endgroup\$
1
\$\begingroup\$

Approach your divisors smarter. They are always smaller than root of n, and come in pairs.

 divisors = []
 (1..(i**0.5)).each do |potential_divisor|
   if i % potential_divisor == 0
     divisors << potential_divisor 
     divisors << i/potential_divisor unless i/potential_divisor == potential_divisor
   end
 end
 q =  divisors.map {|x| x**2 }.reduce{|a,b| a+b }

There are probably even better approaches if you dug into maths, but I got 16 times shorter execution time for m,n = 1, 10_000 this way, so it might just cut it for you.

\$\endgroup\$
0
\$\begingroup\$

My suggestion:

def list_squared(m, n)
   (m..n).each_with_object([]) do |to_check, result|
     to_check_sqrt = Math.sqrt(to_check).to_i

     area = (2..to_check_sqrt).inject(1 + to_check ** 2) do |sum, divisor|
       if to_check % divisor == 0
         sum += divisor ** 2
         sum += (to_check / divisor) ** 2 if divisor != (to_check / divisor)
       end

       sum
     end

     result << [to_check, area] if Math.sqrt(area) == Math.sqrt(area).to_i
   end
end

Edit:

Or this way seems to work too and a little bit faster:

def list_squared2(m, n)
  divisors = {}

  # build a divisor lookup table
  (1..Math.sqrt(n).to_i).each do |divisor|
    (((m / divisor).to_i * divisor)..n).step(divisor) do |divisor_of|
       divisors[divisor_of] ||= []
       divisors[divisor_of] << divisor
       divisors[divisor_of] << divisor_of / divisor if divisor != (divisor_of / divisor)
     end
  end

  # lookup needed values
  (m..n).each_with_object([]) do |to_check, result|
    divisors[to_check] += [to_check]
    area = divisors[to_check].uniq.inject(0) { |sum, divisor| sum + divisor ** 2 }

    result << [to_check, area] if Math.sqrt(area) == Math.sqrt(area).to_i
  end
end
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.