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