Greatest Common Divisor or Highest Common Factor of two numbers, say
b is the largest positive integer that divides both
b. What better way than to take an example to understand what the definition means.
Table of Contents
- How to find GCD of two numbers?
- How to find GCD of a list of numbers?
- Python implementation to find GCD of a list of numbers:
- C++ implementation to find GCD of a list of numbers:
How to find GCD of two numbers?
Let’s find GCD of 24 and 18. As we know it, GCD is HCF i.e. Highest Common Factors. So, let’s find factors of 24 and 18.
Common factors are 1, 2, 3, and 6. Since 6 is the highest of them, GCD of 24 and 18 is 6.
If we were to implement the above process in code, we would:
- Find factors of first number
- Find factors of second number
- Then find the common factors
- And, finally the maximum of the common factors
The process of finding factors is not very time efficient. Time Complexity would be O(N), which can be further improved till O(sqrt N). Still, it is a costly operation. Father of Geometry, Euclid, came up with an out of box algorithm to find GCD of two numbers in a very cost effective way. When we say cost, we are referring to time here.
Formally, Euclid described the algorithm for gcd of two numbers
gcd(a, b) = a, if
b = 0
gcd(a, b) = gcd(b, a), if
b > a
gcd(a, b) = gcd(b, a % b), if
b <= a
Python implementation of the above algorithm:
The above code can be simplified because, when
b > a,
a % b is equal to
a. So if we remove that
if condition, the code will logically remain same, because the last return statement would effectively become
gcd(b, a) when
b > a.
However, sometimes, in Competitive Programming recursive implementations turn out to be slower compared to iterative implementation because the size of input is really large, in the order of billions.
Let’s go ahead and implement an iterative version of the above code.
Analysis of this short Python code:
- We loop as long as b is greater than zero
- The line
a, b = b, a % bactually stores the value of
aand the value of
a % bin
- Return the value of
Python also comes with built-in function to find GCD. You can import it as
from fractions import gcd.
It is worth implementing a C++ version of the above implementation since C++ is way faster than Python.
It is quite tricky to fall for the trap that the Time Complexity is O(a%b). It is not so. There’s a great discussion on stackoverflow regarding the time complexity of Euclid’s algorithm to find GCD of two numbers. It turns out that the Time Complexity is O(log(a) + log(b))
How to find GCD of a list of numbers?
We iterate over the list and make a call to the
N times (assuming the size of list is
N). In the end, our list will have only 1 integer in it.
Let’s take an example: Say we have to find GCD of
[4, 6, 14, 10]
gcd(4, 6) = 2, now we have
[2, 14, 10]
gcd(2, 14) = 2, now we have
gcd(2, 10) = 2, now we have
, hence our answer is
Python implementation to find GCD of a list of numbers:
C++ implementation to find GCD of a list of numbers:
Got a burning question you wanna get answered? Ask it in the comments.