Last Updated: 8 Jan, 2021
Advanced GCD
Easy
Asked in company
You are given two integers A and B, where A is a small integer and B can have at most 250 digits. Your task is to find GCD(A, B), where GCD is Greatest Common Divisor.
Follow Up :
Can you solve the problem in logarithmic time and constant space complexity?
Input format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test contains two space-separated integers A and B.
Output format :
For each test case, print a single line containing the GCD of A and B.
Constraints :
1 <= T <= 100
1 <= A <= 10^9
1 <= B <= 10^250
Time Limit: 1sec
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
In this solution, we will use the fact that GCD of A and B lies between A and B. So we will check all numbers of 1 to A and the largest number which divides both A and B will be our answer.
Here B can have 250 digits to check whether B is divisible by X or not we use the below approach.
- Let us assume B has n digits as d1d2…dn-1dn
- Now we can separate all digits of B using powers of 10 and using modular arithmetic operations such as addition and multiplication we can check if X divides B or not.
We can implement the above approach by –
- Declare a variable to store gcd of A and B, say answer.
- Run a loop from x = 1 to A, and do:
- If x divides both A and B i.e. A % x == 0 and B % x == 0 then set answer as x.
- Finally, Return the answer.
In this solution, we will use the fact that GCD of A and B belong to the divisor of A.
So we will calculate all divisors of A and the highest divisor of A which divides both A and B will be our answer.
We can calculate all divisors of A in sqrt(A) time complexity by running a loop from 1 to sqrt(A).
To check whether B is divisible by the divisor of A or not we will use the previous approach.
Steps :
- Declare a variable to store gcd of A and B, say answer.
- Run a loop from x = 1 to x = sqrt(A), and do:
- If x divides A then if x or A/x divides B set answer as x or A/x. If both of them divide B then set answer as A/x.
- Finally, Return the answer.
In this solution, we will use the Euclid algorithm.
First, we will do modulo of B with A then we will calculate their GCD using the Euclid algorithm.
Steps :
- Declare a variable to store gcd of A and B, say answer.
- Calculate B modulo A i.e. B%A.
- Calculate gcd of two numbers using gcd function and store it in answer.
- Finally, Return the answer.
Description of the gcd function :
Int gcd(a, b) :
- If b== 0 then return a.
- Else return gcd(b,a%b)
In this solution, we will use the Euclid algorithm.
First, we will do modulo of B with A then we will calculate their GCD using the Euclid algorithm.
Unlike the previous solution this time we will calculate gcd iteratively using loops.
Steps :
- Declare a variable to store gcd of A and B, say answer.
- Calculate B modulo A i.e. B%A.
- Calculate gcd of two numbers using gcd function and store it in answer.
- Finally, Return the answer.
Description of the gcd function :
Int gcd(a, b) :
- Run a loop until b>0 and do:
- a = a%b
- swap(a,b)
- Return a.