# 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, The above relation only holds for two numbers, 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.
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, arr, …….., arr[i-1]). This can be done easily as LCM(arr, arr, …., 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 ` `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; ` ` `  `    ``// ans contains LCM of arr, ..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); ` `    ``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

 ` `

Output :

`252`

Related Article :

## tags:

Mathematical GCD-LCM Mathematical