Hello Everyone,

Given an array of positive integers, find LCM of the elements present in array.

Examples:

Input : arr[] = {1, 2, 3, 4, 28}

Output : 84

Input : arr[] = {4, 6, 12, 24, 30}

Output : 120

In this post a different approach is discussed that doesn’t require computation of GCD. Below are steps.

- Initialize result = 1
- Find a common factors of two or more array elements.
- Multiply the result by common factor and divide all the array elements by this common factor.
- Repeat steps 2 and 3 while there is a common factor of two or more elements.
- Multiply the result by reduced (or divided) array elements.

**Illustration :**

Let we have to find the LCM of arr[] = {1, 2, 3, 4, 28} We initialize result = 1. 2 is a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 2, 14} result = 2 2 is again a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 1, 7} result = 4 Now there is no common factor that appears in two or more array elements. We multiply all modified array elements with result, we get. result = 4 * 1 * 1 * 3 * 1 * 7 = 84

Below is the implementation of above algorithm.

`// C++ program to find LCM of array without`

`// using GCD.`

`#include<bits/stdc++.h>`

`using`

`namespace`

`std;`

`// Returns LCM of arr[0..n-1]`

`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;`

`}`

`// Driver code`

`int`

`main()`

`{`

` `

`int`

`arr[] = {1, 2, 3, 4, 5, 10, 20, 35};`

` `

`int`

`n = `

`sizeof`

`(arr)/`

`sizeof`

`(arr[0]);`

` `

`cout << LCM(arr, n) << `

`"\n"`

`;`

` `

`return`

`0;`

`}`

**Output:**

420