Java Program to Find GCD of n numbers (Array)

Problem: Write a Java program to find GCD of n numbers or array of n numbers.

Example:

Input:   [16, 8, 24]
Output:  8

Input:   [16, 8, 24, 4]
Output:  4

Greatest Common Divisor (GCD) of two or more positive numbers is the largest possible integer which divides each of them.

For example, GCD of 16, 8, and 24 is 8.

The trick to calculate the GCD of multiple numbers is to use the gcd of two numbers with the third one.

For example, first, we will calculate the GCD of the first two numbers of the array (say x), then we will calculate the gcd of the x and the third number (say y) then again we will compute gcd of y and the fourth number.

This process will repeat until the last number. The final GCD which we get will be the GCD of the whole array.

Here is the implementation of the algorithm in Java.

class Main {
 
  public static void main(String[] args) {
    int array[] = {16, 8, 24, 4};
    int result = array[0];
 
    //Loop through the array and find GCD
    //by combining the GCD of previous numbers 
    for(int i=1; i<array.length; i++){
      result = findGCD(array[i], result);
    }
    System.out.print("GCD: "+result);
  }
 
  //function to find GCD of two numbers
  public static int findGCD(int a, int b){
    if(b == 0)
      return a;
    return findGCD(b, a%b);
  }

}

Output

8

In this tutorial, we learned to find GCD of n numbers in Java programming language.