Algorithm for computing LCM (least common multiple)

Question

I'm trying to implement this algorithm for computing LCM (from the cut-the-knot website). This is my Java code:

public class LcmAlgorithm {

public static void main(String[] args) {
    long[] input = { 28, 50, 14 };
    System.out.println(lcm(input));
}

private static long lcm(long[] inputs) {
    long[] compute = inputs.clone();
    while (!allEqual(compute)) {
        int minIx = minValueIndex(compute);
        compute[minIx] += inputs[minIx];
    }
    return compute[0];
}

private static boolean allEqual(long[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] != arr[i + 1])
            return false;
    }
    return true;
}

private static int minValueIndex(long[] arr) {
    long min = java.lang.Long.MAX_VALUE;
    int ix = 0;

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
            ix = i;
        }
    }
    return ix;
}
}

It works, but I'm pretty new to Java and I'm not sure my code is optimal (or maybe it's embarrassing...?). I'd like to hear what do you think of my code and how I can improve it. (BTW, I have a background in .NET programming.)

Thanks.

Answer 1

I've included my review comments in the revised code below as program comments, unmistakable because there weren't any comments in the OP. Hmm. That's not a good sign. Though, I can't say that I've helped that much. Backward-looking reviewer comments make a poor substitute for useful forward-looking developer comments.

public class LcmAlgorithm {

    /* Making "main" the only public member clearly limits this as a 
       stand-alone "toy", and that's OK -- it is what it is.

       Yet, you might want to get in the habit of deciding up front which
       functions are purposely permanently private and which you'd
       consider exposing as public in a "real world" implementation.
       This makes your intent clearer to a reviewer (or your future self).

       On the other hand, arguably, you should only expose something as public 
       when/if you have to 
       (because you have an actual external caller -- at least a unit test).
       With that in mind, a good short-term compromise might be to comment 
       your intent on the private declaration with e.g. '// candidate for public'.
    */

    public static void main(String[] args) {
        long[] input = { 28, 50, 14 };
        // Use the Object, Luke.
        LcmAlgorithm lcmAlgorithm = new LcmAlgorithm(input);
        System.out.println(lcmAlgorithm.lcm());
    }

    // Was named "inputs" but its role is more important than its origin.
    // Note: some people prefer plurals for collection names.
    // Whatever you choose, be consistent 
    // -- not "input" here and "inputs" there.
    private final long[] increment;

    // Was "compute" -- don't verb your data names
    // ("sum" sits on the verb/noun fence).
    private long[] sum;

    private LcmAlgorithm(long[] input) { // candidate for public
        assert input.length > 0;
        // Initializing 'increment' here 
        // (vs. with an argument to lcm) allows declaration as final
        increment = input.clone();
        // Initializing both 'increment' and initial 'sum' here
        // saves re-computes if lcm is called more than once.
        sum = input.clone();
    }

    // The name LcmAlgorithm.lcm seems a little redundant
    // -- some alternatives are "compute", stressing the action
    // (perhaps too much?) or "result".
    // "result" may be especially apropos since if you call the
    // function a second time on the same object, you get the
    // result again with very little computation.
    private long lcm() { // candidate for public
        while (!allSumsEqual()) {
            int minIx = minSumIndex();
            sum[minIx] += increment[minIx];
        }
        return sum[0];
    }

    // The next two methods have been slightly simplified, including
    // being made instance methods to get implicit
    // access to the array member, and better leveraging
    // the asserted first element.
    private boolean allSumsEqual() {
        final long firstSum = sum[0];
        for (int i = 1; i < sum.length; i++) {
            if (firstSum != sum[i])
                return false;
        }
        return true;
    }

    private int minSumIndex() {
        long min = sum[0];
        int minIx = 0;

        for (int i = 1; i < sum.length; i++) {
            if (sum[i] < min) {
                min = sum[i];
                minIx = i;
            }
        }
        return minIx;
    }
}

Answer 2

Your code is fine and should be pretty fast. The only downside is that it takes a while to understand exactly what you are doing. Also if you have no control about the input of your program you need to validate that it at some point (normally right after the user made his input). Your code would throw NullPointerExceptions and ArrayIndexOutOfBoundsExceptions.

You stated that you are new with Java so I rewrote your code to use some of the standard libraries and used classes for an easier understanding of the used algorithm.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LcmAlgorithm {

    public static void main(String[] args) {
        //ArrayList implements the interface List
        List<LcmNumber> input = new ArrayList<LcmNumber>();
        input.add(new LcmNumber(3));
        input.add(new LcmNumber(6));
        input.add(new LcmNumber(8));
        System.out.println(lcm(input));   
    }

    private static long lcm(List<LcmNumber> input) {
        //I added this to show how to validate parameters
        //The left part of the condition will be executed first and if already returning false the right part won't be executed
        //This is important because no NullPointerException will be thrown this way
        if(input == null || input.size() == 0){
            throw new IllegalArgumentException("The argument must have at least a size of one");
        }

        //Collections provide a lot of useful methods for manipulating Lists
        //If you work with Arrays the class Arrays will be helpful
        while (Collections.min(input).compareTo(Collections.max(input))!=0) {
            Collections.min(input).increment();
        }

        return input.get(0).getCurrentValue();
    }
}

//Comparable is necessary so the Collections class can do its magic. It defines the method compareTo
class LcmNumber implements Comparable<LcmNumber>{

    private long currentValue;
    private long startValue;

    public LcmNumber(long number){
        startValue = currentValue = number;
    }

    public long getCurrentValue(){
        return currentValue;
    }

    public void increment(){
        currentValue += startValue;
    }

    @Override
    // compareTo expects the following for the returned integer:
    // - negative means this number is smaller than otherNumber
    // - zero means this number is equal to otherNumber
    // - positive means this number is larger than otherNumber
    public int compareTo(LcmNumber otherNumber) {
        //I am using the already implemented compareTo Method of the Long class for convenience
        return (Long.valueOf(currentValue)).compareTo(otherNumber.getCurrentValue());
    }

}

Answer 3

You can use an enhanced for loop here:

private static boolean allEqual(long[] arr) {
    for (long value : arr) {
        if (arr[0] != value)
            return false;
    }
    return true;
}

An optimization idea would be computing allEqual and minValueIndex in one go, but I guess that would hurt readability.