trjhtr

The problem is to find LCM of two numbers. I have tried to solve the problem in two ways. First by using the LCM formula :

LCM (a,b)= a*b/GCD(a,b).

Second, by finding out the multiples of each number and then finding the first common multiple.
Below are the codes that I have written:

Code 1:

#Using the LCM formula LCM = a*b / gcd(a,b)
def LCM(x , y):
 """ define a function LCM which takes two integer inputs and return their LCM using the formula LCM(a,b) = a*b / gcd(a,b) """
 if x==0 or y == 0:
 return "0"

 return (x * y)/GCD(x,y)

def GCD(a , b):
 """ define a function GCD which takes two integer inputs and return their common divisor""" 
 com_div =[1]
 i =2
 while i<= min(a,b):
 if a % i == 0 and b % i ==0:
 com_div.append(i)
 i = i+1
 return com_div[-1]

print LCM(350,1)
print LCM(920,350) 

Code 2:

#Finding the multiples of each number and then finding out the least common multiple
def LCM(x , y):
 """ define a function LCM which take two integerinputs and return their LCM"""
 if x==0 or y == 0:
 return "0"
 multiple_set_1 = 
 multiple_set_2 = 
 for i in range(1,y+1):
 multiple_set_1.append(x*i)
 for j in range(1,x+1):
 multiple_set_2.append(y*j)
 for z in range (1,x*y+1):
 if z in multiple_set_1:
 if z in multiple_set_2:
 return z
 break

print LCM(350,450)

I want to know which one of them is a better way of solving the problem and why that is the case. Also suggest what other border cases should be covered.

About Version 1:

GCD(a, b) has a time complexity of $ O(min(a, b))$ and requires an
array for intermediate storage. You could get rid of the array by
iterating over the possible divisors in reverse order, so that you
can early return if a common divisor is found.

About Version 2:

LCM(x , y) has a time complexity of $ O(xy)$ and requires two
arrays for intermediate storage, so this worse than version 1.
You could improve this by pre-computing only the multiples of one number,
and then test the multiples of the other number (in reverse order)
until you find a common multiple, and then early return.

Common issues:

• LCM should always return a number, your code returns the string
  "0" in some cases.




• Both functions take integer arguments (according to the docstring
  ) but do not produce sensible results for negative input.



• 
  

  The usage of whitespace in your code is inconsistent. Examples:

  
  
  

  if x==0 or y == 0:
  i =2
  

  
  



• More PEP8 coding style
  violations (most of them related to spacing) can be detected by checking
  your code at PEP8 online.

A better algorithm

The "Euclidean Algorithm" is a well-known method for computing the greatest common
divisor, and superior to both of your approaches.

It is already available in the Python standard library:

>>> from fractions import gcd # Python 2
>>> from math import gcd # Python 3
>>> gcd(123, 234)
3

This should be used as the basis for implementing an LCM
function.

Have a look at https://rosettacode.org/wiki/Greatest_common_divisor#Python,
if you want to implement the GCD yourself (for educational purposes),
for example

def gcd_iter(u, v):
 while v:
 u, v = v, u % v
 return abs(u)

This is short, simple, needs no additional space, and fast:
the time complexity is (roughly) $ =O(log(max(a, b))$
(see for example What is the time complexity of Euclid's Algorithm).