CODEWITHSUNDEEP
python-3.x
Jigish Parikh
Jigish Parikh

Reputation: 75

How to find which part of code requires optimization?

Given two integers m, n (1 <= m <= n) find all integers between m and n whose sum of squared divisors is itself a square. 42 is one such a number.

Code works correctly on sample inputs but it is rejected by automatic code checker and reports timeout error and asks to optimize the code...

while m < n :
    list_divisors = []
    temp_list = []
    total = 0 

    for number in range (m+1) :
      if m%(number+1) == 0 :
          list_divisors.append(number+1)

    for number in list_divisors :
        total+= number*number

Codewars does not show what test cases it is failing for. It just shows Execution Timed Out (12000 ms) error. Below test cases passed during sample check.

Test.assert_equals(list_squared(1, 250), [[1, 1], [42, 2500], [246, 84100]])
Test.assert_equals(list_squared(42, 250), [[42, 2500], [246, 84100]])
Test.assert_equals(list_squared(250, 500), [[287, 84100]])

Upvotes: 1

Views: 50

Answers (2)

zedfoxus
zedfoxus

Reputation: 37119

Try this based on your code. No data gets stored in a list. Total is the sum of squared of whole divisors. Then, if square-root of that total is a whole number, return the list.

import math

def list_squared(number):

    total = 0
    for x in range(1, number+1):
        if number % x == 0:
            total += x*x

    bounds = math.sqrt(total)
    if math.ceil(bounds) == math.floor(bounds):
        return [number, total]
    else:
        return False


def all_numbers(start, end):
    numbers = []
    for x in range(start, end+1):
        data = list_squared(x)
        if data != False:
            numbers.append(data)

    return numbers

x = all_numbers(1, 10000)
print(x)

1..10000 checks takes 4.7s. I am sure it can be optimized further. Does this help you?

Even faster

Switching these two lines:

    total = 0
    for x in range(1, number+1):

with

    total = 1 + number*number
    for x in range(2, math.ceil((number+1)/2)):

will cut down your runtime to around half.

Even faster..er

def list_squared(number):
    total = 0
    x = 1
    while x <= math.sqrt(number):
        if number % x == 0:
            if (number/x == x) :
                total += x*x
            else :
                total += x*x + (number/x)*(number/x)
        x += 1

    bounds = math.sqrt(total)
    if math.ceil(bounds) == math.floor(bounds):
        return [number, total]
    else:
        return False

If you were to change list_squared a bit to loop through only square root of the number, you will get a runtime of half a second. The idea behind it is https://www.geeksforgeeks.org/find-divisors-natural-number-set-1/.

Let's take 42 as the number. Square root is 6.48. Let's just use 6. Start with 1. 42 is divisible by 1. 42 is also divisible by the result the division, which is 42.

Go to 2. 42 is divisible by 2. The result is 21. So, 21 is also a whole divisor. Repeat that through 6 and you've covered all divisors for 42. That cuts your runtime to sqrt(n) instead of half.

Upvotes: 1

elethan
elethan

Reputation: 17003

It looks like you never update the values of m or n. So if m < n is True on the first iteration of your loop, it will always be True and your while loop will be infinite. This would explain the timeout, probably because Codewars stops your code from executing if it hasn't finished after 12000ms.

To remedy this, you will have to update either m or n inside your while loop so that eventually the condition m < n evaluates to False, at which point your code will "drop through" the while loop.

Upvotes: 0

Related Questions