# Sum of differences between products and LCMs

I've been trying to solve this Codewars problem https://www.codewars.com/kata/56e56756404bb1c950000992

In this kata you need to create a function that takes a 2D array/list of non-negative integer pairs and returns the sum of all the "saving" that you can have getting the LCM of each couple of number compared to their simple product.

without importing any extra Python library/module.

My code passes al tests but it gets the "Execution Timed Out (12000 ms)" How can I solve this?

Here's my code:

def sum_differences_between_products_and_LCMs(pairs):

result = 0

# calculating LCM
for x, y in pairs:
if x > y:
greater = x
else:
greater = y

while(True):
if x == 0 or y == 0:
lcm = 0
break
else:
if((greater % x == 0) and (greater % y == 0)):
lcm = greater
break
greater += 1

result += ((x*y) - lcm)
return result

• Please include the problem text verbatim. Sep 3, 2022 at 14:31
• Did you read the full description? There is a tip at the bottom about an algorithm to try. Sep 3, 2022 at 14:35
• @Reinderien you got it now. Thanks. Sep 3, 2022 at 15:17
• @Josiah yes :( still don't get it :( Sep 3, 2022 at 15:18
• You're doing trial division to get the greatest common divisor. As the challenge says, you should read about Euclids algorithm. Sep 3, 2022 at 16:00

I finally solved it with the following code (I basically decide to split the arguments of the formula into variables to calculate the LCM):

def sum_differences_between_products_and_LCMs(pairs):

if pairs:

gcd = [] #variable for the gcd
for x, y in pairs:
while(y):
x, y = y, x % y
gcd.append(x)

prod = [] #variable for the product
for x, y in pairs:
prod.append(x * y)

lcm = [] #variable for the lcm
for p in range(len(prod)):
if gcd[p] == 0:
lcm.append(0)
else:
lcm.append(int(prod[p] / gcd[p]))

result = 0
for i in range(len(lcm)):
result += (prod[i] - lcm[i]) # answering the problem question

return result
return 0 # if pairs is empty, return 0

• Welcome to Code Review! Thanks for posting this code. It's a good idea to summarise which changes you made, and why - a self-answer ought to review the code, just like any other answer. Sep 3, 2022 at 21:24