Write a java program to find the lcm of array i.e more than 2 numbers.
Example:
1 2 3 4 5 | Input: [8, 2, 4, 16] Output: 16 Input: [21, 7, 6] Output: 42 |
Recommended: GCD of Array
To find the lcm of array we will use gcd because:
For 2 number LCM = (n1*n2)/GCD.
But this is not valid for more than 2 numbers i.e LCM != (n1*n2*n3)/GCD.
Thus to find lcm of the whole array we will have to deal with two numbers at a time and use its result for the next number.
Suppose LCM of the first two numbers of the array (i.e array[0] and array[1]) is lcm1, for next iteration we will find the LCM of lcm1 and array[2] as lcm2, then for 3rd iteration LCM of lcm2 and array[3] would be lcm3 and so on.
The last LCM value i.e the LCM of lcm(n-1) and arra[n] would be the LCM of the whole array.
For this, we will loop through the array and use Lcm of previous two numbers * array[n] / GCD to find the lcm of the array.
Let’s see how we can do it in Java.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Main { public static void main(String[] args) { int array[] = {8, 4, 2, 16}; int lcm = array[0];; int gcd = array[0]; //Loop through the array and find GCD //use GCD to find the LCM for(int i=1; i<array.length; i++){ gcd = findGCD(array[i], lcm); lcm = (lcm*array[i])/gcd; } System.out.println("LCM: "+lcm); } //function to find GCD of two numbers public static int findGCD(int a, int b){ if(b == 0) return a; return findGCD(b, a%b); } } |
Output
1 | LCM: 16 |
If you have any doubts or suggestion then comment below.