In this article, we have presented an algorithm to find the Greatest Common Divisor (GCD) of all elements of an array efficiently.

Reading time: 10 minutes | Coding time: 5 minutes

Introduction

The Greatest Common Divisor (GCD) of two or more integers can be defined as the largest positive integer that divides all of the integers.
For example,

gcd(4, 8, 10) = 2

as 2 is the greatest number that divides all three numbers

GCD can be computed using many methods like by using

• Prime Factorization
• Euclidian Algorithm
• Binary GCD Algorithm

For this article, we will be sticking to the euclidean algorithm for implementing the GCD calculations.

Pseudocode

Find the gcd of array by iteratively calculating the intermediate gcd at each element

The steps of the algorithm include:

• initialize the result to the first value in the array
• for each subsequent element
  • find the GCD using euclid's algorithm of the intermediate result and the current element
  • reassign this value to the result variable
• return the result

The steps of the Euclid's algorithm include:

• At each step in the iteration
  • replace a with b
  • replace b with (a mod b)
• until the final pair is (d, 0), where d is the greatest common divisor

function gcd(a, b)
    while b != 0 do
        a, b = b, a % b
    end
    return a

result = arr[0]
for i = 1 to n-1
    result = gcd(result, arr[i])

Time & Space Complexity

As we perform the Euclid's algorithm n times for an array of size n, the time complexity would be n * T(Euclid's)

• Worst case time complexity: O(n * h), where h = log(b). This happens when a and b are two consecutive Fibonacci numbers
• Average case time complexity: O(n * (12/(π^2)logalog2. This is calculated using probabilistic distribution.
• Best case time complexity: O(n), that happens when all array elements are the same and Euclid's algorithm takes only O(1) for each iteration
• Space complexity: Θ(1)

Implementation

Following is the implementation of our approach in Python:

def gcd(a, b):
   while b:
       a, b = b, a % b

def gcd_arr(arr, n):
   res = arr[0]
   for i in range(1, n):
       print("gcd(", res, ",", arr[i], ")", end="")
       res = gcd(res, arr[i])
       print("=", res)
   return res

arr = [2, 4, 6, 80]
print("GCD of the array is :", gcd_arr(arr, 4))

Applications

• Reducing fractions for maths
• To compute the modular inverse for the RSA algorithm
• Solving modular linear equations
• A classic example of the usage
  • A rectangular floor measures 300 cm×195 cm. What is the largest square tiles that can be used to cover the floor exactly?

With this article at OpenGenus, you must have a strong hold of how to find the GCD of a set of numbers.