Problem

Submissions

Hints & solutions

Discuss

Advanced GCD

Easy

0/40

7 upvotes

Asked in company

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2 
3 1
50 25

Sample Output 1 :

1
25

Explanation :

For the first test case, 
A = 3 and B = 1 
So GCD (3, 1) = 1

For the second test case
A = 50 and B = 25 
So GCD(50, 25) = 25

Sample Input 2 :

2
5 555555555555555555555555555555555555555
1 232222244444222223444222222422444444444424

Sample Output 2 :

5
1

Explanation :

For the first test case, 
A = 5 and B = 555555555555555555555555555555555555555
So GCD(A, B) = 5 since 5 is the largest number which divides both A and B.

For the second test case
A = 1 and B = 232222244444222223444222222422444444444424
So GCD(A, B) = 1 since GCD of any number with 1 is 1 itself.

Hint 1

Hint 2

Hint 3

Hint 4

Think of a solution using brute force.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute force

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.

E:\coding ninjas\problem 13 gcd\latexgcd.png

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:
1. 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.

Time Complexity

O(A * D), where A is the number given in the problem, and D is the total number of digits in number B.

In the worst case, we are running a loop from 1 to A which takes O(A) time and checking if x divides B or not takes O(D) time. Hence the overall complexity will be O(A*D).

Space Complexity

O(1).

In the worst case, a constant space is required.

(100% EXP penalty)

Advanced GCD

Console