Difficulty: Medium, Asked-in: Microsoft, SAP Labs
Key takeaways
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
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:
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:
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
}
Note: Gradually we will update more exciting content to this blog!
Enjoy learning, enjoy mathematics!
There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?
A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any party that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name. You are given the list of people present at the party. And we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?