×

Search anything:

# Find GCD of all elements in an array

#### Algorithms List of Mathematical Algorithms Culture Get this book -> Problems on Array: For Interviews and Competitive Programming

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
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
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?

## Question

#### What would be the GCD of the array {11, 121, 264, 143}

2
13
11
5
gcd(11, 121) = 11 => gcd(11, 264) = 11 => gcd(11, 143) = 11

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