Java Programs›Numbers›Find GCD of Multiple Numbers

Find GCD of Multiple Numbers in Java

intermediate· Numbers · Number Theory

Problem

The GCD of a whole group of numbers is the largest number that divides every one of them evenly — it can be built up by combining the GCD of just two numbers at a time.

Given an array of integers, find the greatest common divisor shared by all of them.

Input

[24, 36, 60]

Output

GCD: 12

Java Program

Java

public class GCDOfMultipleNumbers {
    static int gcd(int a, int b) {
        if (b == 0) return a; // base case: a is the GCD once b runs out
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[] nums = {24, 36, 60};
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            result = gcd(result, nums[i]); // fold the next number into the running GCD
        }

        System.out.println("GCD: " + result);
    }
}

▶ Run Code

Output

GCD: 12

Core Logic

The GCD of a group of numbers is the same as folding the two-number GCD across the whole array, one element at a time — gcd(gcd(a, b), c) equals gcd(a, b, c).

How It Works

1result starts out holding the first element of the array.
2A loop visits every remaining element, replacing result with gcd(result, nums[i]) at each step.
3Combining the running GCD with one more number at a time keeps the pairwise gcd() helper doing all the real work.
4After the last element has been folded in, result holds the GCD of the entire array.

For [24, 36, 60], gcd(24, 36) is 12, and gcd(12, 60) is still 12 — the GCD shared by all three.

💡

Key Point: This works because GCD is associative — combining numbers two at a time, in any order, always arrives at the same final answer.

Complexity

Time Complexity: O(n × log(min pair))Space Complexity: O(1)

Why: gcd() is called once per remaining element, and each call costs O(log) time via the Euclidean algorithm, so the total scales with both the array's length and that per-call cost.

Key Concepts

running GCDEuclidean algorithmfor loop

Approach 2: Java 8

Java

import java.util.Arrays;

public class GCDOfMultipleNumbersStream {
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[] nums = {24, 36, 60};
        // Folds gcd() across every element, the same way the manual loop does
        int result = Arrays.stream(nums).reduce(GCDOfMultipleNumbersStream::gcd).getAsInt();
        System.out.println("GCD: " + result);
    }
}

▶ Run Code

Output

GCD: 12

Core Logic

The same fold-two-at-a-time idea is exactly what Stream.reduce() is built for — no manual loop variable is needed.

How It Works

1Arrays.stream(nums) converts the int[] into an IntStream.
2.reduce(...) combines every element using the given operator, carrying the running result forward the same way the manual loop's result variable does.
3The method reference ::gcd supplies the pairwise combining logic without writing a lambda body out longhand.
4.getAsInt() unwraps the OptionalInt that reduce() without an identity value returns.

Reducing [24, 36, 60] with gcd folds 24 and 36 down to 12 first, then folds that 12 with 60, landing on the same answer, 12.

💡

Key Point: reduce() without an explicit identity value returns an OptionalInt because it has no sensible answer for an empty stream — worth remembering before calling .getAsInt() on untrusted input.

Complexity

Time Complexity: O(n × log(min pair))Space Complexity: O(1)

Why: reduce() still calls gcd() once per remaining element, the same total work as the manual loop, just expressed as a stream fold.

Key Concepts

Streamreduce()method reference

← Previous

Find Fibonacci Number at Position N

Find GCD (Euclidean Algorithm)

Related Programs

Numbersintermediate

Calculate Combination (nCr)

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number