I am doing coding challenge named Integers: Recreation One in Codewars.

Challenge => 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.

def list_squared(m, n):
    lst = list()
    for num in range(m, n+1):
        total= 0
        for i in range(1, num//2 +1):
            if num % i == 0:
                total += i**2
        total += num**2

        if (total**(1/2)) % 1 == 0:
            lst.append([num, total])

    return lst

My code works for sample tests but when I try to submit it, it is giving me " Execution Timed Out " error. I think I have to make this more efficent but don't know how to do it. How can I make the code more efficent?

1 Answers

0
tevemadar On Best Solutions

An implementation of the sqrt idea:

def list_squared(m, n):
    lst = list()
    for num in range(m, n+1):
        total = 0
        sqrt = int(math.sqrt(num))
        for i in range(1, sqrt+1):
            q,r=divmod(num,i)
            if r == 0:
                total += i*i + q*q
        if sqrt*sqrt == num:
            total -= num

        if math.sqrt(total) % 1 == 0:
            lst.append([num, total])

    return lst

It seems to work. A couple things which may or may not make sense:

  • I do not know if **(1/2) or math.sqrt performs better, it could be checked. However I feel sqrt is more readable. Of course if you are not allowed to use the math library, stick with **
  • It is rather probable that x*x is faster than x**2, it could be checked too
  • At assembly level, the quotient and the remainder are produced in a single step, which may or may not be true for Python. However this is why I used divmod (so q*q replaces (num/i)*(num/i), or (num/i)**2)

In reality these details probably do not matter at all, shortening the inner loop should be the main trick.


@H.E.K.: you "felt" that the loop can be shortened somehow, via the /2 thing, but in reality it has to be square root.
If i is divisor of num, num/i is also a divisor of num. And if i starts increasing from 1, num/i starts decreasing from num/1 (so from num itself). As time passes, they will meet somewhere, and that is sqrt(num). Increasing i above sqrt(num) ends up with checking a divisor-pair which you have seen already. An example with 20:

i   20/i
1   20
2   10
3   <something fraction>
4   5    <--- this is the last step when we encounter a new divisor
5   4    <--- here the divisors are "old", we have seen 4 and 5 already
6   <something fraction>
......

so the divisors are 1,20,2,10,4,5 - and we did not have to check 5...20 separately, it was enough to check 1...4=(int)sqrt(20), which is a significant gain.