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[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:

, where**O(n * h)**`h = log(b)`

. This happens when a and b are two consecutive Fibonacci numbers - Average case time complexity:

. This is calculated using probabilistic distribution.**O(n * (12/(Ï€^2)logalog2** - Best case time complexity:

, that happens when all array elements are the same and Euclid's algorithm takes only O(1) for each iteration**O(n)** - 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?

## Question

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

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