Performance upgrade

Question

I'm trying to solve an online exercise that ask us to calculate the least common multiple of n numbers. The entry give us a number that represent the n numbers that will come on the next line, and then the line with the numbers we must use to calculate the lcm.

The online judge runs Openjdk1.7 and with the code here exposed i get 0.09 seconds of execution. I saw a guy who get 0.008 with java.

Can you please help me to improve the performance of my solution?

Thank You!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Problema381 {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

       int x = Integer.valueOf(reader.readLine());
       int res, temp, aaux, bux, a, b;
       while(x != 0) {

           res = 1;

           String[] strs = reader.readLine().trim().split("\\s+");

           for (int j = 0; j < x; j++) {

               temp = 1;               
               aaux = res;
               a = aaux;               
               bux = Integer.valueOf(strs[j]);
               b = bux;            
               do {
                   temp = bux;
                   bux = aaux % bux; // % is remainder
                   aaux = temp;
               } while (bux != 0);

               res =  a * (b / temp);
           }
           System.out.println( res );
           x = Integer.valueOf(reader.readLine());
       }
       reader.close();
    }
}

I don't know if it makes a difference, but lose the `Integer.valueOf`. Work with primitive `int` not with the wrapper. https://stackoverflow.com/questions/7355024/integer-valueof-vs-integer-parseint — Thilo, Feb 11 '20 at 00:13
As the computation is rather fast, the problem might be with something else, e.g., your `split`, which compiles the regex every time. Just guessing. `+++` [A faster gcd algorithm](https://github.com/google/guava/blob/master/guava/src/com/google/common/math/IntMath.java#L404). — maaartinus, Feb 11 '20 at 13:34

score 0 · Answer 1 · edited Feb 11 '20 at 13:35

0

Take a look at the simple algorithm for least common multiple. This may get you some speedup.

edited Feb 11 '20 at 13:35

maaartinus

44,714
32
161
320

answered Feb 11 '20 at 01:53

Ray Tayek

9,841
8
50
90

Performance upgrade

1 Answers1