FOR FREE YEAR SOLVED

LCM of N numbers

Back to Programming

Description

LCM stands for Least Common Multiple. Here the program is written to find the LCM of ‘n’ numbers. The value of ‘n’ and ‘n’ numbers is taken as input from the user. For example, if the number of elements be 3, and the given numbers are   12, 15, 18, then we have to find the LCM of 12,15 and 18. Here, first the GCD of each pairs are calculated and we know that,

GCD×LCM=Product of two numbers.

Therefore, LCM= Product of two numbers/GCD.

For the above example, first pair of number is 12, 15.

The GCD of these two numbers: 3.

According to the aforesaid formula:

LCM= 

Now, we have to find the LCM of 60 and 18. The GCD of these pair is 6. 

Therefore,

LCM=

Therefore, the Least Common Multiple of 12, 15 and 18 is 180.

Algorithm

INPUT: The value of ‘n’ and ‘n’ numbers

OUTPUT: LCM of ‘n’ numbers

PROCESS:

Step 1: [Taking the input]

               Read n

               For i=0 to n-1 repeat

                              Read a[i]

               [End of ‘for’ loop]

Step 2: [Function to find the ‘GCD’ of two numbers stored in ‘x’ & ‘y’]

               While x≠y repeat

                              If x>y then

                                             Set x<-x-y

                              Else

                                             Set y<-y-x

                              [End of ‘if-else’]

               [End of ‘while’ loop]

               [Returning the gcd]

               Return x

[End of the function]

Step 3: [Function to find the ‘LCM’]

               Set l<-a[0]

               [Finding the lcm]

               For i=1 to n-1 repeat 

                              Set l<-(((a[i]×l))/(gcd(a[i],l)))

               [End of ‘for’ loop]

               Print "The lcm is: l"

[End of function]               

Step 4: Stop.

Code

TIME COMPLEXITY:

for (i=1;i<n;i++)-------------------------------O(n) 

        l=(((a[i]*l))/(gcd(a[i],l))); 

The time complexity of finding LCM is O(n) where ‘n’ is the number of elements.

SPACE COMPLEXITY:

The space complexity of this program is O(1) as it requires a constant number of memory spaces for any given input.