The Problem
Find the LCM of the given array of positive numbers.
The LCM (Least Common Multiple) of two or more numbers is the smallest number that is evenly divisible by all numbers in the set.

Examples

Input: arr[] = {1, 2, 3, 4, 8, 28, 36}
Output: 504

Input: arr[] = {16, 18, 20, 30}
Output: 720

We have explored 2 approaches:

• Method 1 (using GCD)
• Method 2 (without using GCD)

Method 1 (using GCD)

We know that,
LCM(a, b) = (a*b)/GCD(a, b), where GCD stands for Greatest Common Divisor.
The above formula stands true only for two numbers taken at a time.

Approach
The approach to the problem is simple with the formula.

1. Initialize the answer as arr[0].
2. Iterate from arr[1] to arr[n-1] (assuming the array size is n), and the find the LCM of the current answer and the ith number of the array. In other words, LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i]).

Example

Input: arr[] = {1, 2, 3, 8}

Approach:

Step 0:
Initialize ans = arr[0] = 1

Step 1:
LCM(ans, arr[1]) = LCM(1, 2) = 2

Step 2:
LCM(ans, arr[2]) = LCM(2, 3) = 6

Step 3:
LCM(ans, arr[3]) = LCM(6, 8) = 24

Output: 24

Solution
C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// GCD of 'a' and 'b'
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
// Function to find
// LCM of array elements
int findlcm(int arr[], int n)
{
    // Initialize answer
    int ans = arr[0];
 
    for (int i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));
 
    return ans;
}
 
int main()
{
    int arr[] = { 1, 2, 3, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findlcm(arr, n);
    return 0;
}

Output

24

Time Complexity: O(n), since we're traversing through all the array elements.
Space Complexity: O(1), no auxiliary space is used.

Method 2 (without using GCD)

Approach

1. Initialize answer as 1.
2. Find a common factor of any two or more elements in the array. Divide the multiples of that common factor in the array by the factor and multiply the answer by the same.
3. Repeat Step 2 until there is no common factor left.
4. Multiply the remaining elements of the array with the current answer to obtain the final answer.

Example

Input: arr[] = {3, 6, 9, 10}

Approach:

Step 0:
Initialize ans = 1

Step 1:
2 is a common factor in
two or more elements.
Divide the multiples by 2
arr[] = {3, 3, 9, 5}
Multiply ans by 2
ans = 1 * 2 = 2

Step 2:
3 is a common factor in
two or more elements.
Divide the multiples by 3
arr[] = {1, 1, 3, 5}
Multiply ans by 3
ans = 2 * 3 = 6

Step 3:
No more common factors left.
Multiply the ans with
the remaining elements
ans = 6 * 1 * 1 * 3 * 5 = 90

Output: 90

Solution
C++

#include<bits/stdc++.h>
using namespace std;
 
long long int LCM(int arr[], int n)
{
    // Find the maximum value in arr[]
    int maxi = 0;
    for (int i=0; i<n; i++)
        if (maxi < arr[i])
            maxi = arr[i];
 
    // Initialize answer
    long long int ans = 1;
 
    // Find all factors that are present in
    // two or more array elements.
    int x = 2;  // Starting from minimum factor of 2
    while (x <= maxi)
    {
        // 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;
 
            ans = ans * x;
        }
        else
            x++;
    }
 
    // Then multiply all reduced array elements
    for (int i=0; i<n; i++)
        res = res*arr[i];
 
    return res;
}
 
int main()
{
    int arr[] = {3, 6, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << LCM(arr, n) << "\n";
    return 0;
}

Output

90

Time Complexity: O(n^2) in the worst case, since there are two loops involved.
Space Complexity: O(1), no auxiliary space is used.

With this article at OpenGenus, we can find the LCM of an array of numbers efficiently.