3
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.