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