LCM of all the numbers in an array in Java
Solution 1
If you change your gcd function to
public static int gcd(int a, int b){
if (a<b) return gcd(b,a);
if (a%b==0) return b;
else return gcd(b, a%b);
}
it should work okay.
Solution 2
This is the program to find lcm and gcd for array of n numbers using formula lcmgcd=ab
public class Main
{
public static void main(String[] args) {
int a[]={63,105,210};
int lcm=1,fir=lcm,res=0;
for(int i=0;i<a.length;i++)
{
int sec=a[i];
lcm=(fir*sec)/gcd(fir,sec);
fir=lcm;
}
for(int j=0;j<a.length;j++)
{
res=gcd(res,a[j]);
}
System.out.println("lcm is "+lcm+" "+"gcd is "+res);
}
public static int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
}
Anindya Guha
I'm a Computer Science and Mathematics student at Colgate University in Hamilton, New York. My hometown is Dhaka, Bangladesh.
Updated on August 02, 2022Comments
-
Anindya Guha over 1 year
I have an array of ints, and I'm trying to find the LCM (least common multiple) of all the values in the array. I've written an
lcm
method separately; it takes two values as input, and returns the lcm. Mylcm
method works perfectly fine, but when I use it to find the LCM of all the values I get a wrong answer.Here are my
gcd
andlcm
methods:public static int gcd(int a, int b){ if (a<b) return gcd(b,a); if (a%b==0) return b; else return gcd(a, a%b); } public static int lcm(int a, int b){ return ((a*b)/gcd(a,b)); }
This is what I have for the lcm of the array values:
public static int lcmofarray(int[] arr, int start, int end){ if ((end-start)==1) return lcm(arr[start],arr[end-1]); else return (lcm (arr[start], lcmofarray(arr, start+1, end))); }
When I put in an array that has the numbers 1 to 5 as
arr
, 0 asstart
and the length of the array asend
, I get 30 as the answer, while I want 60. When I put in an array containing all the numbers from 1 to 10, I get 840 instead of 2520. I really can't explain that.The algorithm should work--I've worked it out in my head. Can't figure out what the problem is with my code.
Any help will be appreciated.