Please tell me why its wrong (LCM & GCD )
Question : Given an array of n numbers, find LCM of it.
Since LCM(a,b) = a*b / GCD(a,b), here is my original code:
class GFG {
// the simple 2 integers recursive to find their GCD.
static int getGcd(int a, int b){
while(a != b){
if(a >b){
a = ab;
}else{
b= ba;
}
}
return a;
}
// find GCD in an array that has more than two integers.
static int Gcd(int[] newArray){
int gcd = newArray[0];
for(int i=1; i<newArray.length; i++){
gcd = getGcd(gcd,newArray[i]);
}
return gcd;
}
static int Lcm(int[] newArray){
int multi =1;
for(int i=0; i< newArray.length; i++){
multi = multi* newArray[i];
}
return (multi/gcd);
}
public static void main (String[] args) {
int[] newArray = { 2, 7, 3, 9, 4 };
System.out.println(Gcd(newArray));
System.out.println(Lcm(newArray));
}
}
But when I run this code, it shows some error:
prog.java:33: error: cannot find symbol
return (multi/gcd);
^
symbol: variable gcd
I don't know how to fix it. Please help me to correct my code... Thanks!!!
4 answers

There is no gcd defined in the Lcm() function. The gcd last defined was in Gcd() function, while this is not a global variable Lcm() cannot use it.
Maybe you mean this?
static int Lcm(int[] newArray){ int multi =newArray[0]; int gcd = 0; for(int i=1; i< newArray.length; i++){ gcd = getGcd(multi, newArray[i]); if(gcd == 1) { multi = multi * newArray[i]; }else { multi = multi * newArray[i] / gcd; } } return multi; }
Use this could generate the result. You could just have a think about this. We start from 2, multi is 2, and the next value is 7. The gcd for 2 and 7 is 1, so the lcd will be 14. Then we use 14 to compare 3, gcd is also 1, so just multi them is 42. Then use 42 compare 9, we found that 9 have the gcd with 42 is 3, so we use 42/3 is 14, then use 14 and 9, gcd is 1, give multi 14x9 is 126. Then use 126 and 4, the gcd is 2, so multi is 126/2 = 63, and 63 and 4 gcd is 1, so finally multi is 63x4 is 252.
If you have a look of any two numbers, no matter is [3,7],[50,5],[20,10],[100,10000],[52,57],[3,81], the lcm is always a*b/gcd. In this case we could get the answer.

I hope This Logic May helpful to u .
// 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)); } }

Logic For GCD of two numbers is ,
// Java program to find GCD of two numbers class Test { // Recursive function to return gcd of a and b static int gcd(int a, int b) { // Everything divides 0 if (a == 0  b == 0) return 0; // base case if (a == b) return a; // a is greater //u r missing the logic here..................... if (a > b) return gcd(ab, b); else return gcd(a, ba); } // Driver method public static void main(String[] args) { int a = 98, b = 56; System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b)); } }
Please see the logic, you should iterate till a=b , u r iterating only once.

I hope this may helps u.
Thank you