LCM of all the numbers in an array in Java

Question

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.

Don't use recursion here, just loop through the array finding consecutive LCMs. — arshajii, Jul 17 '13 at 01:19
I'm not sure if I understand how you're setting it up, but is it looks like your first if statement will call the LCM function on the same number. For example, if start = 0, end = 1, then you're returnning lcm(arr[0], arr[0]) = arr[0] — Kon, Jul 17 '13 at 01:21
I guess I could use a loop instead, but at this point I want to know why my code isn't working. @Kon I wanted the base case to be: when two elements are left in the array, find the lcm of the two elements. (The input array will never have less than two elements.) Should I change it to (end-start==2) instead? — Anindya Guha, Jul 17 '13 at 01:27
Your code actually works for me, and produces the expected results. http://ideone.com/Afk4pO — arshajii, Jul 17 '13 at 01:27
Your code seems working for me. Can you provide your implementation of `lcm`? — johnchen902, Jul 17 '13 at 01:28
For example, if your array has length 2, then its maximum index is end = 2. Then you're asking if start - end == 1, but you're starting at 0 and 2 - 0 != 1, so it does NOT think there are 2 elements in the array. One way of fixing it would be to change ==1 to ==2. That's one way. A loop would be smarter. — Kon, Jul 17 '13 at 01:29
@Kon Just debugged. His construct will make duplicate `lcm`, but not missing anyone. — johnchen902, Jul 17 '13 at 01:33
@arshajii, johnchen902 I added my gcd and lcm methods above-- they seemed to work for me. — Anindya Guha, Jul 17 '13 at 01:34

score 6 · Accepted Answer · answered Dec 15 '13 at 20:41

6

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.

answered Dec 15 '13 at 20:41

user2514440

138
2
5

score 1 · Answer 2 · answered Apr 23 '21 at 05:14

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);
    }
}

Akanksha · Answer 3 · 2018-04-13T07:01:06.807

0

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;
}

edited Apr 13 '18 at 07:01

answered Jan 24 '18 at 15:59

Akanksha

181
3
8

I'm quite sure, you are also making recursive call. Could you highlight, how your code is different ? – Ravi Jan 24 '18 at 16:05
1

No, I am not making recursive calls. I am using iterative approach. There is only first statement if(a – Akanksha Jan 25 '18 at 06:48
I see. But, I didn't understand the logic of interchanging `a` and `b` value. BTW, it gives wrong output. https://ideone.com/aLKxuL – Ravi Jan 25 '18 at 10:48
Yeah, I checked. Interchanging a and b not required. But It is anyway giving me correct output everytime. Can you pls mention the usecase where output is not correct? Also, feel free to add your solution or modify mine. Thanks – Akanksha Jan 25 '18 at 13:53
1

I have shared a link in my last comment. Your code gives wrong output. If I will change your code, then answer will completely change :-) – Ravi Jan 25 '18 at 13:56
Hi Ravi Thanks! I got the mistake. Will fix it in sometime. GTG. – Akanksha Jan 25 '18 at 14:08

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

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);
    }
}

LCM of all the numbers in an array in Java

4 Answers4

Linked