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. My lcm
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
and lcm
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 as start
and the length of the array as end
, 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.
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.