**Difficulty:** Medium, **Asked-in:** Microsoft, SAP Labs

**Key takeaways**

- The Euclidean algorithm is one of the oldest and most widely known algorithms. It is a method of computing the greatest common divisor (GCD) of two integers m and n.
- One of the best problems to learn problem-solving using recursion (Decrease and conquer strategy).
- It allows computers to do various simple number-theoretic tasks and serves as a foundation for more complicated algorithms in number theory.

Given two non-negative integers m and n, we have to find their greatest common divisor or GCD or HCF**.** It is the largest number which is a divisor of both m and n.

**Some important note**

- If any one of the integer is 0, then the GCD is the other number. It means, if m = 0, n != 0, then GCD(m, n) = n. Similarly, if m != 0, n = 0, then GCD(m, n) = m.
- When both m and n are 0, their GCD is undefined i.e. it can be any arbitrarily large number!
- If the smaller of the two numbers can divide the larger number then the GCD is the smaller number.

**Examples**

Input: m = 40, n = 32, Output: 8

Explanation: Integers 1, 2, 4, and 8 can divide both 40 and 30. Here 8 is the largest number, So, GCD (40, 30) = 10.

Input: m = 60, n = 40, Output: 20

Explanation: Integers 1, 2, 4, 5, 10 and 20 can divide both 60 and 40. Here 20 is the largest number, So, GCD (40, 30) = 10.

**Solution Idea**

As we have seen earlier, if a smaller number is divisible by the larger number then GCD is equal to the smaller number. Otherwise, GCD will be definitely smaller than the smaller of both numbers!

Suppose m > n and m are not divisible by n. Then we need to find the largest number x (x < m and x < n) which is divisible by both m and n. One observation is: Integers from n/2 + 1 to n - 1 will not be the GCD of both m and n because all these integers are not divisible by the smaller number n. So the first best guess for GCD would be x = n/2.

So one basic idea would be to run a loop from i = n/2 to 2 and check whether the current integer i divides both m and n. If yes, then the value is required GCD.

**Solution Pseudocode**

```
int gcd(int m, int n)
{
int minValue = min(m, n)
if (m % minValue == 0 && n % minValue == 0)
return minValue
for (int i = minValue/2; i >= 2; i = i - 1)
{
if (m % i == 0 && n % i == 0)
return i
}
return 1
}
```

Suppose m > n and GCD(m, n) = x. Based on the definition of the GCD, x is the largest number that divides both m and n. Now let's think about the difference m - n, which is smaller than the largest number!

If x divides m and n, then it would also divide the number m - n. Here is the simple proof: Suppose, m = ax and n = bx, where a > b. Then m - n = ax - bx = (a - b)x i.e. if we divide m - n with x, we will get the value a - b.

So the idea is: The common divisors of m and n would be the same as the common divisors of m - n, and n, where m and n are positive integers. GCD(m, n) = GCD(m - n, n).

This is a recursive equation where we solve the problem of finding the GCD of m and n using the smaller problem of finding the GCD of m - n and n. In other words: the greatest common divisor of two positive integers consists of replacing the larger number with the difference of the numbers and repeating this until the two numbers are equal: that is their greatest common divisor!

For example, to compute GCD(48,18), one proceeds as follows:

- GCD(48,18) = GCD(48 - 18,18) = GCD(30, 18)
- GCD(30, 18) = GCD(30 - 18, 18) = GCD(12, 18)
- GCD(12, 18) = GCD(12, 18 - 12) = GCD(12, 6)
- GCD(12, 6) = GCD(12 - 6, 6) = GCD(6, 6)

Now both numbers are equal, which is the base case => So GCD(48, 18)= 6. Note: This method can be very slow if one number is much larger than the other. Think!

**Recursive Pseudocode Implementation**

```
int gcd(int m, int n)
{
if (m == 0)
return n
if (n == 0)
return m
if (m == n)
return m
if (m > n)
return gcd(m - n, n)
return gcd(m, n - m)
}
```

**Iterative Pseudocode Implementation**

```
int gcd (int m, int n)
{
while (m != n)
{
if (m > n)
m = m - n
else
n = n - m
}
return m
}
```

The Euclidean algorithm is more efficient method of calculating GCD where the difference of the two numbers m and n is replaced by the remainder of the division of m by n. This is the idea of the Euclid algorithm: the gcd of two integers m and n with m > n equals the gcd of n and m mod n (the remainder when m is divided by n). In other words, GCD(m, n) = GCD(n, m mod n).

As we know from the idea of the mod operator, the remainder of the division of m by n can be written as m mod n. This is a recursive algorithm where we replace the input size (m, n) with (n, m mod n) repeatedly until the pair is (x, 0), where x is the greatest common divisor.

**Recursive Structure:** GCD(m , n) = gcd(n, m mod n)

**Base case:** GCD(m , n) = m, if n =0

Proof: If we divide m with n, we can write: m = kn + m mod n, where k is an integer (the quotient). Suppose any number x that divides both m and n, then we write it further:

=> m/x = (kn)/x + (m mod n)/x.

Here, m/x and (kn)/x are integers, then (m mod n)/x must be an integer. Hence any number x that divides both m and n should divide m mod n as well. For example, to compute gcd(48,18), the computation is as follows:

- GCD(48,18) = GCD(18, 48 mod 18) = GCD(18, 12)
- GCD(18, 12) = GCD(12, 18 mod 12) = GCD(12, 6)
- GCD(12, 6) = GCD(6, 12 mod 6) = GCD(6, 0)

Now we reached the base case => So GCD(48, 18)= 6.

**Recursive Pseudocode Implementation**

```
int gcd(int m, int n)
{
if (n == 0)
return m
return gcd(n, m % n)
}
```

**Iterative Pseudocode Implementation**

```
int gcd (int m, int n)
{
while (n)
{
m = m % n
swap(m, n)
}
return m
}
```

Extended Euclidean algorithm also finds integer coefficients x and y such that: For every pair of whole numbers m and n, there are two integers x and y such that mx + ny = gcd(m, n).

**Recursive Implementation**

```
int gcdExtended(int m, int n, int *x, int *y)
{
if (m == 0)
{
*x = 0
*y = 1
return n
}
int x1, y1
int gcd = gcdExtended(n%m, m, &x1, &y1)
*x = y1 - (n/m) * x1
*y = x1
return gcd
}
```

**Iterative Implementation**

```
int gcd(int m, int n, int &x, int &y)
{
*x = 1, *y = 0
int x1 = 0, y1 = 1
int m1 = m, n1 = n
while (n1)
{
int quotient = m1 / n1
int temp = x
*x = x1
x1 = temp - quotient * x1
temp = y
*y = y1
y1 = temp - quotient * y1
temp = m1
m1 = n1
n1 = temp - quotient * n1
}
return m1
}
```

- What would be the time complexities of the above approaches? What would be the worst-case scenario of the Euclidean algorithm?
- Explore the other methods of calculating the GCD of two numbers.
- Explore various properties related to the GCD.
- How do we find the LCM of two numbers using the GCD?
- Explore various applications of GCD computer science.

- Divide and Conquer Algorithm
- Binary Search Algorithm
- Merge Sort Algorithm
- Quick Sort Algorithm
- Analysis of Recursion
- Iteration vs Recursion Comparison

**Note:** Gradually we will update more exciting content to this blog!

**Enjoy learning, enjoy mathematics!**

Gold For 7 days of Work

You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?

Important Math Topics for Data Structures and Algorithms

Just like programming, math is one of the core parts of learning data structures and algorithms. We mainly use math to analyse efficiency of various algorithms. But sometimes, the problem itself contains mathematical property or requires some mathematical insight to find a solution.

N-Bulb in a Circle Puzzle

You have given n-bulbs connected in a circle with a switch for each bulb. The connection is such that if you change the state of anyone bulb may be on or off, it will toggle the state of its adjacent bulbs. All the bulbs are initially switched off. You have to find the number of steps such that all the bulbs are switched on.