LCM of given array elements

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

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.