GCD of several integers Exercise: Write a method that returns the gcd of an unspecified number of integers.


What I did:


Created a for loop that stores integers in an array. The array length is increased every time the else statement is reached. The loop will break upon receiving '0'.
Created a method to find the gcd. This method sorts the array using Arrays.sort. The first element of the array will be 0. The lowest integer (index 1) is assigned to the variable min.
To compute the gcd, I created a for loop that assigns min to i. I decrement this variable until the modulo operation for count % numbers.length - 1 equals 0. This indicates that a gcd has been found for all integers and will break out of the main for loop. The variable count will increment when an integer in the array is divisible by the current divisor.


I would really appreciate any feedback you can give me.

public class Exercise_07_14 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("Enter numbers: ");
        int[] numbers = new int[1];

        for (int i = 0; i &lt; numbers.length; i++) {
            int number = input.nextInt();

            if (number == 0)
                break;
            else
                numbers[i] = number;

            numbers = incrementArraySize(numbers);
        }

        int gcd = getGCD(numbers);

        String output = "";

        for (int i = 1; i &lt; numbers.length; i++) {
            if (i == numbers.length - 1)
                output += numbers[i];
            else
                output += numbers[i] + ", ";
        }

        System.out.println("The GCD of [" + output + "] is: " + gcd);
    }

    public static int getGCD(int... numbers) {
        Arrays.sort(numbers);

        int min = numbers[1];
        int gcd = 1;

        for (int i = min; i &gt; 1; i--) {
            int count = 0;

            for (int k = 1; k &lt; numbers.length; k++) {
                if (numbers[k] % i != 0)
                    break;
                else
                    count++;
            }

            if (count == (numbers.length - 1)) {
                gcd = i;
                break;
            }
        }

        return gcd;
    }

    public static int[] incrementArraySize(int[] array) {
        int[] tempArray = array;
        array = new int[tempArray.length + 1];

        System.arraycopy(tempArray, 0, array, 0, tempArray.length);

        return array;
    }
}
There are some issues, such as not using obvious built-in solutions, an inefficient algorithm and what looks like a logic error possibly caused by having odd array-growing logic.

I'll start with the error. In int min = numbers[1]; you assume that there are at least two numbers. That may not be true, if the user immediately enters 0 - which raises the question of what the GCD of the empty set is (0 or 1, depending on who you believe), but whatever it should be, it's bad form to crash with an out-of-bounds exception.

The odd array-growing logic is probably part of that problem, it leaves a spurious 0 in the array which you thereafter actively ignore - it's simpler to not have it there to begin with. Anyway, you wanted an array that can change size - that's usually called ArrayList which, conveniently, already exists. You can also avoid saving up the input entirely, by computing the GCD while reading the input.

The GCD algorithm is strange and inefficient. It's not the familiar GCD algorithm, which is already a strike against it by itself since that makes it hard to tell what it's doing, and there is no redeeming quality. This is an algorithm with a very bad worst case, as much as O(min*N) (if the GCD turns out to be 1). I strongly recommend using the modulo-based version of the Euclidean algorithm, which is efficient and recognizable, or maybe Binary GCD if you want something different. In the unlikely case that you rejected it because it takes only two inputs, of course gcd(a, b, c) = gcd(gcd(a, b), c) and so on, so you can simply loop over your input and call GCD on the gcd-so-far and the number from the input.

Or, as mentioned, you could compute the GCD while reading the input, something like this:

int gcdSoFar = 0;

while (true) {
    int number = input.nextInt();
    if (number == 0)
        break;

    gcdSoFar = gcd(number, gcdSoFar);
}

System.out.println("The GCD of the input is: " + gcdSoFar);


This loses the print-back of the input, if you want to preserve that you could use an ArrayList. By the way, in Java 8 you can use String.join(", ", list) to make a comma-separated string from your list, you don't have to do that manually.