LCM of all the numbers in an array in Java

问题:

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.

回答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.

回答2:

The above method looks good but it is getting stack overflow error because of recursive calls:

Please find the below solution:

    public int findHCF(int a, int b) {

    if (b>a){
        return findHCF(b, a);
    }

    while(a%b!=0){

        int temp = b;
        b=a%b;
        a=temp;
    }
    return b;
}

回答3:

Brief idea about the logic behind the code-

LCM(a,b)=a*b/HCF(a,b)

You can do this using the following code-

package hackerrank;

/*
 * Author Hirak JD
 */
import java.util.Arrays;

public class LCM {
    public static void main(String args[]) {
        int[] set= {2,3,6,8};
        int lcm=1;
        for(int each:set) {
            lcm=calculateLcm(lcm,each);
        }

        System.out.println("LCM for "+Arrays.toString(set)+" is : "+lcm);

    }

    private static int calculateLcm(int lcm, int each) {
        return lcm*each/gcd(lcm,each);
    }

    private static int gcd(int val1, int val2) {
        if(val1==0||val2==0)
            return 0;

        if(val1==val2)
            return val1;

        if(val1>val2)
            return gcd(val1-val2,val2);
        return gcd(val1,val2-val1);
    }
}