|
Answer» We know that LCM (x, y) = (x * y) / GCD (x, y). We have to extend this idea to an array of numbers. Let's imagine we have an array arr[] with n members for which the LCM must be calculated. Our algorithm's major steps are as FOLLOWS: - Set res = arr[0] as the first value.
- Iterate over all of the array's elements, from i = 1 to i = n-1.
Our lcm, which is stored in res, is LCM of (arr[0], arr[1],........, arr[i-1]) at the ITH iteration. LCM (arr[0], arr[1],...., arr[i]) = LCM (ans, arr[i]). As a result, we only need to do res = LCM (ans, arr[i]) = (ans * arr[i]) / gcd at the i'th iteration (ans, arr[i]).
//C++ PROGRAM to find the LCM of n elements of an array#INCLUDE <bits/stdc++.h>using namespace std; typedef long long int ll; //the function that finds//GCD of 'x' and 'y'int GCD(int x, int y){ if (y == 0) return x; return GCD(y, x % y);} //Driver Codeint main(){ int a[] = { 11, 7, 3, 9, 4 }; int len = sizeof(a) / sizeof(a[0]); // Initializing result which will store the lcm ll res = a[0]; // res contains LCM of a[0], ..a[i] // after i'th iteration, for (int i = 1; i < len; i++) res = (((a[i] * res)) / (GCD(a[i], res))); cout<<res<<ENDL; return 0;}Output: 2772
|
