HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Algorithm for computing LCM (least common multiple)

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
lcmalgorithmforleastmultiplecommoncomputing

Problem

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.

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#9106, answer score: 3

Revisions (0)

No revisions yet.