Online Ethical Hacking Course

Apply Now

Examples

GCD of Array in Java (GCD of n Numbers Program)

There are countless scenarios in mathematics and computer science where understanding the Greatest Common Divisor (GCD) plays a pivotal role. 

Whether you're working on number theory problems, simplifying fractions, optimizing algorithms, or even solving real-world challenges like managing fractions of time, the GCD is a fundamental concept that can simplify and streamline your solutions.

In this comprehensive tutorial, we will learn how to find the GCD of an array of numbers in Java, commonly referred to as "gcd of n numbers." 

Concepts to Learn:

GCD of Array in Java Using Euclidean Algorithm

In this example, we use the Euclidean Algorithm to find the GCD of an array of numbers in Java programming.

Code

import java.util.Arrays;

public class GCDOfArray {
    public static int findGCD(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int result = nums[0];
        for (int num : nums) {
            result = gcd(result, num);
        }
        
        return result;
    }
    
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public static void main(String[] args) {
        int[] numbers = {8, 12, 16};
        int gcd = findGCD(numbers);
        System.out.println("GCD of " + Arrays.toString(numbers) + " is: " + gcd);
    }
}

Output

GCD of [8, 12, 16] is: 4

Explanation

The Euclidean Algorithm is an efficient method to calculate the GCD of two numbers by iteratively taking the remainder of the larger number divided by the smaller number until the remainder becomes zero.

Here's a step-by-step breakdown of the process:

  • We initialize result with the first number in the array, which is 8.

  • We iterate through the array and for each number, we calculate its GCD with the current result using the gcd function.

  • The gcd function implements the Euclidean Algorithm to find the GCD of two numbers.

  • After iterating through all the numbers in the array, we obtain the GCD of the entire array, which is 4 in this case.

  • We print the result, indicating that the GCD of the array [8, 12, 16] is 4.

Full Stack Developer Course

GCD of n Numbers in Java

To find the GCD of n numbers in Java, you can adapt the Euclidean Algorithm mentioned earlier to handle any number of inputs:

Code

import java.util.Arrays;

public class GCDOfNNumbers {
    public static int findGCD(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int result = nums[0];
        for (int num : nums) {
            result = gcd(result, num);
        }
        
        return result;
    }
    
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public static void main(String[] args) {
        int[] numbers = {8, 12, 16, 24, 32, 40, 56, 64};
        int gcd = findGCD(numbers);
        System.out.println("GCD of " + Arrays.toString(numbers) + " is: " + gcd);
    }
}

Output

GCD of [8, 12, 16, 24, 32, 40, 56, 64] is: 4

Explanation

This program is similar to the previous Java program to find the GCD of an array, but it can handle an array of n numbers. Just replace the int[] numbers array with your desired set of numbers, and the program will calculate their GCD.

GCD of n Numbers in Java Using Recursion

Here's a Java program to find the GCD of n numbers using recursion:

Code

public class GCDOfNNumbers {
    public static int findGCD(int[] nums, int n) {
        if (n == 1) {
            return nums[0];
        }
        return gcd(nums[n - 1], findGCD(nums, n - 1));
    }

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

    public static void main(String[] args) {
        int[] numbers = {8, 12, 16, 24};
        int n = numbers.length;
        int gcd = findGCD(numbers, n);
        System.out.println("GCD of numbers is: " + gcd);
    }
}

Output

GCD of numbers is: 4

Explanation

In this program, we use a recursive function findGCD to find the GCD of n numbers. The function takes an array of numbers nums and the value of n, which represents the number of elements in the array.

The findGCD function recursively computes the GCD of the last n numbers by repeatedly calling itself with a smaller n until n becomes 1. The base case is when n is 1, in which case the GCD of a single number is itself.

The gcd function is a standard recursive implementation of the Euclidean Algorithm to find the GCD of two numbers.

Finally, in the main method, we call findGCD with the array of numbers and its length to find the GCD of all the numbers

Learn Next: