## Monday, June 20, 2016

### LCM of given array elements - GeeksforGeeks

LCM of given array elements - GeeksforGeeks
Given an array of n numbers, find LCM of it.

We know,
The above relation only holds for two numbers,
The idea here is to extend our relation for more than 2 numbers. Let’s say we have an array arr[] that contains n elements whose LCM needed to be calculated.
The main steps of our algorithm are:
1. Initialize ans = arr[0].
2. Iterate over all the elements of the array i.e. from i = 1 to i = n-1
At the ith iteration ans = LCM(arr[0], arr[1], …….., arr[i-1]). This can be done easily as LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i]). Thus at i’th iteration we just have to do ans = LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i])
`int` `gcd(``int` `a, ``int` `b)`
`{`
`    ``if` `(b==0)`
`        ``return` `a;`
`    ``gcd(b, a%b);`
`}`
`// Returns LCM of array elements`
`ll findlcm(``int` `arr[], ``int` `n)`
`{`
`    ``// Initialize result`
`    ``ll ans = arr[0];`
`    ``// ans contains LCM of arr[0],..arr[i]`
`    ``// after i'th iteration,`
`    ``for` `(``int` `i=1; i<n; i++)`
`        ``ans = ( ((arr[i]*ans)) /`
`                ``(gcd(arr[i], ans)) );`
`    ``return` `ans;`
`}`

http://www.geeksforgeeks.org/finding-lcm-two-array-numbers-without-using-gcd/
1. Initialize result = 1
2. Find a common factors of two or more array elements.
3. Multiply the result by common factor and divide all the array elements by this common factor.
4. Repeat steps 2 and 3 while there is a common factor of two or more elements.
5. Multiply the result by reduced (or divided) array elements.
`unsigned ``long` `long` `int` `LCM(``int` `arr[], ``int` `n)`
`{`
`    ``// Find the maximum value in arr[]`
`    ``int` `max_num = 0;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``if` `(max_num < arr[i])`
`            ``max_num = arr[i];`

`    ``// Initialize result`
`    ``unsigned ``long` `long` `int` `res = 1;`

`    ``// Find all factors that are present in`
`    ``// two or more array elements.`
`    ``int` `x = 2;  ``// Current factor.`
`    ``while` `(x <= max_num)`
`    ``{`
`        ``// To store indexes of all array`
`        ``// elements that are divisible by x.`
`        ``vector<``int``> indexes;`
`        ``for` `(``int` `j=0; j<n; j++)`
`            ``if` `(arr[j]%x == 0)`
`                ``indexes.push_back(j);`

`        ``// If there are 2 or more array elements`
`        ``// that are divisible by x.`
`        ``if` `(indexes.size() >= 2)`
`        ``{`
`            ``// Reduce all array elements divisible`
`            ``// by x.`
`            ``for` `(``int` `j=0; j<indexes.size(); j++)`
`                ``arr[indexes[j]] = arr[indexes[j]]/x;`

`            ``res = res * x;`
`        ``}`
`        ``else`
`            ``x++;`
`    ``}`

`    ``// Then multiply all reduced array elements`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``res = res*arr[i];`

`    ``return` `res;`
`}`