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 all 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


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. Commented Sep 3, 2022 at 21:24

Here are some suggestions for the code in your question which are purely for coding style. I don't expect any difference in performance from the code in your question.

Documentation

Add a docstring to describe the function input, the return value and the LCM abbreviation.

Type hints

Also add type hints for the function to complement the documentation.

Ternary

The if/else to set the initial value of greater is simple enough to use a ternary operator. This arguably simplifies the code.

Parentheses

Typically, the parentheses are omitted in while and if statements such as in your code.

Simpler

The if/else/if can be simplified to an if/elif. This has the added benefit of vertically aligning the lcm and breaklines.

The LCM comment is helpful, but it should be moved closer to the code it describes.

Here is new code with the suggestions above:

def sum_differences_between_products_and_LCMs(pairs: list) -> int:
"""
The input is an array of pairs of non-negative integers.
Return the sum of the differences between the product
of the numbers and their least common multiples (LCM).
"""

result = 0

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

# calculating LCM
while True:
if x == 0 or y == 0:
lcm = 0
break
elif (greater % x == 0) and (greater % y == 0):
lcm = greater
break
greater += 1

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