Greatest Common Divisor

Easy
0/40
Average time to solve is 15m
profile
Contributed by
44 upvotes
Asked in companies
CognizantGooglePaytm (One97 Communications Limited)

Problem statement

You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.

The Greatest Common Divisor of any two integers is the largest number that divides both integers.

For Example: 
You are given ‘X’ as 20 and ‘Y’ as 15. The greatest common divisor, which divides both 15 and 20, is 5. Hence the answer is 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains ‘T’, representing the number of test cases. 

The first line of each test case contains two space-separated integers, ‘X’ and ‘Y’, representing the given numbers.
Output Format: 
For each test case, print a single integer representing the Greatest Common Divisor of ‘X’ and ‘Y’.

Print a separate line for each test case.
Note (c++, python): 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= X, Y <= 10^9
Sample Input 1:
2
20 15
8 32
Sample Output 1:
5
8
Explanation:
For the first test case, the greatest common divisor which divides both 15 and 20 is 5. Hence the answer is 5.

For the second test case, the greatest common divisor which divides both 8 and 32 is 8. Hence the answer is 8.
Sample Input 2:
2
98 56
36 60
Sample Output 2:
14
12
Hint

Try to think of a brute force approach by traversing through each factor.

Approaches (2)
Brute Force

In this approach, we know the minimum value of a common factor of two integers is 1, and the maximum value of a common factor is the minimum value of the given two integers. 

Therefore we will maintain a variable ans to store GCD. We set the initial value of ans as 1. We will iterate through the integers from 2 to the minimum of X and Y. We will check for each integer if X and Y are divisible by the integer, then update the ans with the integer. In the end, we return the variable ans.

 

Algorithm:

  • Set the variable ans as 1. The variable ans stores the greatest common divisor of X and Y.
  • Iterate num from 2 to the minimum of X and Y.
    • If X and Y are divisible by num, set ans as num.
  • Finally, return the variable ans.
Time Complexity

O(Min(X, Y)), Where X and Y are the given integers.

 

We are iterating from 2 to the minimum of X and Y to find the greatest common divisor, which takes O(Min(X, Y)) time. Hence, the overall time complexity becomes O(Min(X, Y)).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall space complexity becomes O(1).

Code Solution
(100% EXP penalty)
Greatest Common Divisor
Full screen
Console