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