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:
- Initialize ans = arr[0].
- 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 :
- Finding LCM of more than two (or array) numbers without using GCD
- Inbuilt function for calculating LCM in C++
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
1 Comments