Can someone explain me this logic of computing LCM of a list of numbers. I saw this method on stackoverflow, used it and my solution got accepted… But I don’t understand how this is correct or how we can do this, so can someone explain? (I am mathematically handicapped )
Here is the algorithm for computing LCM
for i=1 to n
a.take i_th number as x
b.reduce(devide) remaining numbers(i+1_th to n_th) by their gcd with x
c.multiply x to ans and take mod of ans
return ans
and here is the LCM computation code
and here is the solution which got AC
http://www.codechef.com/viewsolution/4333825
3 Likes
Normally one finds lcm by this method .For two numbers a and b lcm(a,b)=(a*b)/gcd(a,b). So your algo is same as this one but on much wider scale. So what you are doing is actually reducing reducing all the numbers taken in pairs by their gcd and finally taking all of their product. This was done so as to avoid repeated factors in your lcm and leaves you with the lowest possible value.
Try to work it out in this example and then you can see it for yourself.
4,8,6,15,9
Quick Overview:
The above the algorithm removes all the factors of remaining numbers which are already included in x.
Explanation:
for eg.
Consider 3 numbers 14, 20, 48
8 = 2 * 2 * 2
14 = 2 * 7
80 = 2 * 2 * 2 * 2 * 5
LCM of (8,14,80) = 2 * 2 * 2 * 2 * 7 * 5
Firstly, x=8
Dividing the remaining numbers with gcd will filter all the factors which are already in x(in this case it is 8).
Thus if the number of a particular factor in x is less than than other numbers, then it will add only the extra factors. And if the number is greater, then the no extra factors need to be multiplied.
Therefore it becomes (2 * 2 * 2) * ( 7 ) *(2 * 5). And since all are multiplication operation, you can take mod at each step.
Hope this helps.
4 Likes
