Hello Everyone,
Given an array of n numbers, find LCM of it.
Input : {1, 2, 8, 3}
Output : 24
Input : {2, 7, 3, 9, 4}
Output : 252
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:
- Initialize ans = arr[0].
- 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])
Below is the implementation of above algorithm :
// C++ program to find LCM of n elements
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Utility function to find
// GCD of 'a' and 'b'
int gcd( int a, int b)
{
if (b == 0)
return a;
return 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;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 3, 9, 4 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( "%lld" , findlcm(arr, n));
return 0;
}
Output :
252