Tutorialspoint.dev

LCM of given array elements

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


We know,
 LCM(a, b)=frac{a*b}{gcd(a, b)}
The above relation only holds for two numbers,
 LCM(a, b, c)
eq frac{a*b*c}{gcd(a, b, c)}

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:

  1. Initialize ans = arr[0].
  2. 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++



// 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;
}

Java

// Java Program to find LCM of n elements
public class GFG {
      
    public static long lcm_of_array_elements(int[] element_array)
    {
        long lcm_of_array_elements = 1;
        int divisor = 2;
          
        while (true) {
            int counter = 0;
            boolean divisible = false;
              
            for (int i = 0; i < element_array.length; i++) {
  
                // lcm_of_array_elements (n1, n2, ... 0) = 0.
                // For negative number we convert into
                // positive and calculate lcm_of_array_elements.
  
                if (element_array[i] == 0) {
                    return 0;
                }
                else if (element_array[i] < 0) {
                    element_array[i] = element_array[i] * (-1);
                }
                if (element_array[i] == 1) {
                    counter++;
                }
  
                // Divide element_array by devisor if complete
                // division i.e. without remainder then replace
                // number with quotient; used for find next factor
                if (element_array[i] % divisor == 0) {
                    divisible = true;
                    element_array[i] = element_array[i] / divisor;
                }
            }
  
            // If divisor able to completely divide any number
            // from array multiply with lcm_of_array_elements
            // and store into lcm_of_array_elements and continue
            // to same divisor for next factor finding.
            // else increment divisor
            if (divisible) {
                lcm_of_array_elements = lcm_of_array_elements * divisor;
            }
            else {
                divisor++;
            }
  
            // Check if all element_array is 1 indicate 
            // we found all factors and terminate while loop.
            if (counter == element_array.length) {
                return lcm_of_array_elements;
            }
        }
    }
      
    // Driver Code
    public static void main(String[] args)
    {
        int[] element_array = { 2, 7, 3, 9, 4 };
        System.out.println(lcm_of_array_elements(element_array));
    }
}
  
// Code contributed by Mohit Gupta_OMG

Python

# Python Program to find LCM of n elements
  
def find_lcm(num1, num2):
    if(num1>num2):
        num = num1
        den = num2
    else:
        num = num2
        den = num1
    rem = num % den
    while(rem != 0):
        num = den
        den = rem
        rem = num % den
    gcd = den
    lcm = int(int(num1 * num2)/int(gcd))
    return lcm
      
l = [2, 7, 3, 9, 4]
  
num1 = l[0]
num2 = l[1]
lcm = find_lcm(num1, num2)
  
for i in range(2, len(l)):
    lcm = find_lcm(lcm, l[i])
      
print(lcm)
  
# Code contributed by Mohit Gupta_OMG

C#

// C# Program to find LCM of n elements
using System;
  
public class GFG {
      
    public static long lcm_of_array_elements(int[] element_array)
    {
        long lcm_of_array_elements = 1;
        int divisor = 2;
          
        while (true) {
              
            int counter = 0;
            bool divisible = false;
            for (int i = 0; i < element_array.Length; i++) {
  
                // lcm_of_array_elements (n1, n2, ... 0) = 0.
                // For negative number we convert into
                // positive and calculate lcm_of_array_elements.
                if (element_array[i] == 0) {
                    return 0;
                }
                else if (element_array[i] < 0) {
                    element_array[i] = element_array[i] * (-1);
                }
                if (element_array[i] == 1) {
                    counter++;
                }
  
                // Divide element_array by devisor if complete
                // division i.e. without remainder then replace
                // number with quotient; used for find next factor
                if (element_array[i] % divisor == 0) {
                    divisible = true;
                    element_array[i] = element_array[i] / divisor;
                }
            }
  
            // If divisor able to completely divide any number
            // from array multiply with lcm_of_array_elements
            // and store into lcm_of_array_elements and continue
            // to same divisor for next factor finding.
            // else increment divisor
            if (divisible) {
                lcm_of_array_elements = lcm_of_array_elements * divisor;
            }
            else {
                divisor++;
            }
  
            // Check if all element_array is 1 indicate 
            // we found all factors and terminate while loop.
            if (counter == element_array.Length) {
                return lcm_of_array_elements;
            }
        }
    }
      
    // Driver Code
    public static void Main()
    {
        int[] element_array = { 2, 7, 3, 9, 4 };
        Console.Write(lcm_of_array_elements(element_array));
    }
}
  
// This Code is contributed by nitin mittal

PHP

<?php
// PHP program to find LCM of n elements
  
// Utility function to find
// GCD of 'a' and 'b'
function gcd($a, $b)
{
    if ($b == 0)
        return $a;
    return gcd($b, $a % $b);
}
  
// Returns LCM of array elements
function findlcm($arr, $n)
{
      
    // Initialize result
    $ans = $arr[0];
  
    // ans contains LCM of 
    // arr[0], ..arr[i]
    // after i'th iteration,
    for ($i = 1; $i < $n; $i++)
        $ans = ((($arr[$i] * $ans)) /
                (gcd($arr[$i], $ans)));
  
    return $ans;
}
  
// Driver Code
$arr = array(2, 7, 3, 9, 4 );
$n = sizeof($arr);
echo findlcm($arr, $n);
  
// This code is contributed by ChitraNayal
?>


Output :

252

Related Article :

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

1 Comments

load comments

Subscribe to Our Newsletter