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.
To do this we will use the loop through the array and use 2 numbers at a time to find the lcm of the array.
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.
So the last LCM value i.e the LCM of lcm(n-1) and arra[n] would be the LCM of the whole array.
Let’s do the same 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.