Finding LCM of more than two (or array) numbers without using GCD
Given an array of positive integers, find LCM of the elements present in array.
Examples:
Input : arr[] = {1, 2, 3, 4, 28} Output : 84 Input : arr[] = {4, 6, 12, 24, 30} Output : 120
We have discussed LCM of array using GCD.
In this post a different approach is discussed that doesn’t require computation of GCD. Below are steps.
- Initialize result = 1
- Find a common factors of two or more array elements.
- Multiply the result by common factor and divide all the array elements by this common factor.
- Repeat steps 2 and 3 while there is a common factor of two or more elements.
- Multiply the result by reduced (or divided) array elements.
Illustration :
Let we have to find the LCM of arr[] = {1, 2, 3, 4, 28} We initialize result = 1. 2 is a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 2, 14} result = 2 2 is again a common factor that appears in two or more elements. We divide all multiples by two and multiply result with 2. arr[] = {1, 1, 3, 1, 7} result = 4 Now there is no common factor that appears in two or more array elements. We multiply all modified array elements with result, we get. result = 4 * 1 * 1 * 3 * 1 * 7 = 84
Below is the implementation of above algorithm.
C++
// C++ program to find LCM of array without // using GCD. #include<bits/stdc++.h> using namespace std; // Returns LCM of arr[0..n-1] unsigned long long int LCM( int arr[], int n) { // Find the maximum value in arr[] int max_num = 0; for ( int i=0; i<n; i++) if (max_num < arr[i]) max_num = arr[i]; // Initialize result unsigned long long int res = 1; // Find all factors that are present in // two or more array elements. int x = 2; // Current factor. while (x <= max_num) { // 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; res = res * x; } else x++; } // Then multiply all reduced array elements for ( int i=0; i<n; i++) res = res*arr[i]; return res; } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 10, 20, 35}; int n = sizeof (arr)/ sizeof (arr[0]); cout << LCM(arr, n) << "\n" ; return 0; } |
Java
import java.util.Vector; // Java program to find LCM of array without // using GCD. class GFG { // Returns LCM of arr[0..n-1] static long LCM( int arr[], int n) { // Find the maximum value in arr[] int max_num = 0 ; for ( int i = 0 ; i < n; i++) { if (max_num < arr[i]) { max_num = arr[i]; } } // Initialize result long res = 1 ; // Find all factors that are present in // two or more array elements. int x = 2 ; // Current factor. while (x <= max_num) { // To store indexes of all array // elements that are divisible by x. Vector<Integer> indexes = new Vector<>(); for ( int j = 0 ; j < n; j++) { if (arr[j] % x == 0 ) { indexes.add(indexes.size(), 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.get(j)] = arr[indexes.get(j)] / x; } res = res * x; } else { x++; } } // Then multiply all reduced array elements for ( int i = 0 ; i < n; i++) { res = res * arr[i]; } return res; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 10 , 20 , 35 }; int n = arr.length; System.out.println(LCM(arr, n)); } } |
Python3
# Python3 program to find LCM of array # without using GCD. # Returns LCM of arr[0..n-1] def LCM(arr, n): # Find the maximum value in arr[] max_num = 0 ; for i in range (n): if (max_num < arr[i]): max_num = arr[i]; # Initialize result res = 1 ; # Find all factors that are present # in two or more array elements. x = 2 ; # Current factor. while (x < = max_num): # To store indexes of all array # elements that are divisible by x. indexes = []; for j in range (n): if (arr[j] % x = = 0 ): indexes.append(j); # If there are 2 or more array # elements that are divisible by x. if ( len (indexes) > = 2 ): # Reduce all array elements # divisible by x. for j in range ( len (indexes)): arr[indexes[j]] = int (arr[indexes[j]] / x); res = res * x; else : x + = 1 ; # Then multiply all reduced # array elements for i in range (n): res = res * arr[i]; return res; # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 10 , 20 , 35 ]; n = len (arr); print (LCM(arr, n)); # This code is contributed by chandan_jnu |
C#
// C# program to find LCM of array // without using GCD. using System; using System.Collections; class GFG { // Returns LCM of arr[0..n-1] static long LCM( int []arr, int n) { // Find the maximum value in arr[] int max_num = 0; for ( int i = 0; i < n; i++) { if (max_num < arr[i]) { max_num = arr[i]; } } // Initialize result long res = 1; // Find all factors that are present // in two or more array elements. int x = 2; // Current factor. while (x <= max_num) { // To store indexes of all array // elements that are divisible by x. ArrayList indexes = new ArrayList(); for ( int j = 0; j < n; j++) { if (arr[j] % x == 0) { indexes.Add(j); } } // If there are 2 or more array elements // that are divisible by x. if (indexes.Count >= 2) { // Reduce all array elements divisible // by x. for ( int j = 0; j < indexes.Count; j++) { arr[( int )indexes[j]] = arr[( int )indexes[j]] / x; } res = res * x; } else { x++; } } // Then multiply all reduced // array elements for ( int i = 0; i < n; i++) { res = res * arr[i]; } return res; } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 5, 10, 20, 35}; int n = arr.Length; Console.WriteLine(LCM(arr, n)); } } // This code is contributed by mits |
PHP
<?php // PHP program to find LCM of array // without using GCD. // Returns LCM of arr[0..n-1] function LCM( $arr , $n ) { // Find the maximum value in arr[] $max_num = 0; for ( $i = 0; $i < $n ; $i ++) if ( $max_num < $arr [ $i ]) $max_num = $arr [ $i ]; // Initialize result $res = 1; // Find all factors that are present // in two or more array elements. $x = 2; // Current factor. while ( $x <= $max_num ) { // To store indexes of all array // elements that are divisible by x. $indexes = array (); for ( $j = 0; $j < $n ; $j ++) if ( $arr [ $j ] % $x == 0) array_push ( $indexes , $j ); // If there are 2 or more array // elements that are divisible by x. if ( count ( $indexes ) >= 2) { // Reduce all array elements // divisible by x. for ( $j = 0; $j < count ( $indexes ); $j ++) $arr [ $indexes [ $j ]] = (int)( $arr [ $indexes [ $j ]] / $x ); $res = $res * $x ; } else $x ++; } // Then multiply all reduced // array elements for ( $i = 0; $i < $n ; $i ++) $res = $res * $arr [ $i ]; return $res ; } // Driver code $arr = array (1, 2, 3, 4, 5, 10, 20, 35); $n = count ( $arr ); echo LCM( $arr , $n ) . "\n" ; // This code is contributed by chandan_jnu ?> |
Javascript
<script> // Javascript program to find LCM of array without // using GCD. // Returns LCM of arr[0..n-1] function LCM(arr, n) { // Find the maximum value in arr[] var max_num = 0; for ( var i = 0; i < n; i++) if (max_num < arr[i]) max_num = arr[i]; // Initialize result var res = 1; // Find all factors that are present in // two or more array elements. var x = 2; // Current factor. while (x <= max_num) { // To store indexes of all array // elements that are divisible by x. var indexes = []; for ( var j = 0; j < n; j++) if (arr[j] % x == 0) indexes.push(j); // If there are 2 or more array elements // that are divisible by x. if (indexes.length >= 2) { // Reduce all array elements divisible // by x. for ( var j = 0; j < indexes.length; j++) arr[indexes[j]] = arr[indexes[j]]/x; res = res * x; } else x++; } // Then multiply all reduced array elements for ( var i = 0; i < n; i++) res = res*arr[i]; return res; } // Driver code var arr = [1, 2, 3, 4, 5, 10, 20, 35]; var n = arr.length; document.write( LCM(arr, n) + "<br>" ); // This code is contributed by rrrtnx. </script> |
Output:
420
Time Complexity: O(max * n), where n represents the size of the given array and m represents the maximum element present in the array.
Auxiliary Space: O(n), where n represents the size of the given array.
Contact Us