GCD of several integers

Question

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 < 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 < 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 > 1; i--) {
            int count = 0;

            for (int k = 1; k < 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;
    }
}

Answer 1

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.

Answer 2

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

Using an array and incrementing the size is a little ugly, and it's inefficient. Consider using an ArrayList, which allows for index-based insertion in constant time, and hides all of the size changes (as well as doing them more efficiently).

        for (int i = 0; i < numbers.length; i++) {

You definitely don't want to loop from 0 to numbers.length, when numbers.length is changing. This loop doesn't really capture your stopping condition, which is input.nextInt() == 0. How about: int number; while ((number = input.nextInt()) != 0) ... and in the loop you add the number to your Array(List), without needing to use the break condition.

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

You say:

The first element of the array will be 0

I can't see why this is so, since you don't add 0 to the array, and the user can't input it. Did you test this code? It seems like there is a bug here.

        int gcd = 1;

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

            for (int k = 1; k < numbers.length; k++) {

Regarding these for loops: I prefer to avoid break statements where possible. They tend to be more difficult to understand intuitively, especially in a for loop. As a rule, I prefer my loop to end because of the condition it checks, not because it gets breakd.

                if (numbers[k] % i != 0)
                    break;
                else
                    count++;
            }

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

The contents of the outer for loop - i.e. the inner loop and the if check - could be broken out into a separate function, boolean isDivisor(int[] numbers, int candidate), which could return instead of break. I.e. if (numbers[k] % i != 0) return false; in the for loop, and if you finish the loop without returning, return true;.

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

Overall: aside from the "first item in array is 0" which is either a mistake or a misunderstanding on my part, your code is clean and well-organized. I urge you to 1.) try to use break less often, and rely instead on iterator-based for loops and boolean-based while loops as much as possible, and 2.) read up on ArrayList - it's a very common and useful data structure, and I think it's what you're going for by trying to implement a self-adjusting array.