Given an array of size n, your task is to find the least common multiple or LCM of all the elements of the array.
Examples:
Input : arr = [ 8, 9, 21] Output : 504 Input : arr = [ 2, 4, 3, 8] Output : 24
RECOMMENDED: Maximum Length Subsequence from Ticket Prices Array
Method-1: Prime Fcatorization Method
Unique factorization theorem states that a number can be uniquely identified as a product of prime factors. Using this fact, The lcm will be the product of multiplying the highest power of each prime number together. 8 = 2^3 9 = 3^2 21 = 3 * 7 The highest power of the three prime numbers 2, 3, and 7 is 2^3 , 3^2 , and 7^1 respectively. Therefore lcm(8, 9, 21) = 8 * 9 * 7 = 504
This method is not very efficient as there are no efficient methods for integer factorization.
Method-2: Reduction by Greatest Common Divisor(Efficient)
Mathematically,
lcm(a,b) = abs(a) * abs(b) / gcd(a, b)
Hence the problem of finding lcm is reduced to finding the gcd of the numbers for more than two numbers. The formula can be easily extended as :
lcm(a, b, c) = lcm(a, lcm(b, c)) lcm = lcm * arr[i] / gcd(lcm, arr[i]
This method can be made more efficient by using Euclidian theorem for calculation of gcd which doesn’t require integer factorization. Also, to avoid overflow we take modulo 10^9 + 7. Following is an identity for the same :
(a * b) % c = ((a % c) * (b % c)) % c
Since gcd divides both arr[i] and lcm we perform division first to ensure overflow doesn’t occur.
Below is its implementation:
#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 // Function to find gcd long gcd(long a, long b) { if (b == 0) return a; return gcd(b, a % b); } int main() { int arr[] = {2, 4, 3, 8}; // Initialize lcm as 1 long lcm = 1; int n = 4; for (int i = 0; i < n; i++) { // Take mod 10^9 + 7 to avoid overflow lcm = (((arr[i] % MOD) * (lcm % MOD)) / gcd(lcm, arr[i])) % MOD; } cout << "Lowest common multiple is: " << lcm << endl; }
Output:
Lowest common multiple is: 24
Time Complexity: O(n)
Space Complexity: O(1)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.