CODEWITHSUNDEEP
python
Xue Chuancong
Xue Chuancong

Reputation: 3

How to improve this solution?

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.

Examples:

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]

list_squared(42, 250) --> [[42, 2500], [246, 84100]]

above is the instructor of the question.

I have a problem when do the practice of Coderwars. my code have passed all tests, but have a error "timeout", it means my code is not very good.how can I improve it. Below is my solution.

from math import sqrt
def get_div(x):
    s = []
    for i in range(1,x):
        if x%i == 0:
            # print i, x/i
            s.append(i)
            s.append(x/i)
    return set(s)

def list_squared(m, n):
    p = []
    for i in range(m,n):
        if i == 1:
            p.append([1,1])
            continue
        s = sum(a**2 for a in get_div(i))
        if float(sqrt(s)).is_integer():
            p.append([i,s])
    return p

Upvotes: 0

Views: 477

Answers (2)

Thomas
Thomas

Reputation: 1377

Based on the answer to this question Algorithm to calculate the number of divisors of a given number and the comment from @devin-white you may want to try the following solution.

def divisors_squared_sum(x):
    limit = x
    squared_sum = 0
    if x==1:
        return 1
    i = 1
    while True:
        if x % i == 0:
            limit = x / i
            if limit != i:
                squared_sum += limit**2
            squared_sum += i**2
        i += 1
        if i >= limit:
            return squared_sum

def list_squared2(start, end):
    res = []
    for i in xrange(start, end):
        squared_sum = divisors_squared_sum(i)
        sqrt_sum = np.sqrt(squared_sum)
        if int(sqrt_sum) == sqrt_sum:
            res.append([i, squared_sum])

    return res

I get the following results:

In [24]: %timeit list_squared(1, 250)
100 loops, best of 3: 3.6 ms per loop

In [25]: %timeit list_squared2(1, 250)
100 loops, best of 3: 1.96 ms per loop

Upvotes: 1

Devin White
Devin White

Reputation: 31

Two things I would suggest:

1) Instead of get_div and returning an array, why not change it to get_div_squared_sum and just return the sum? You're only using that array to sum anyway so if you just calculate the sum in the function then you lose an entire for loop.

2) It's been mentioned already but you only need to go to sqrt(x) in order to get every possible divisor.

Upvotes: 1

Related Questions