gcd
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.

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:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

gcd

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.

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:

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

Accepted Answer

Again a standard and easy math problem.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n)Explanation:

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)).

Java (SE 1.8)


/*
	Time Complexity: O(Min(X, Y))
	Space Complexity O(1)
	
	Where X and Y are the given integers.
*/

public class Solution {
	public static int findGcd(int x, int y) {

		// Set initial answer as 1
		int ans = 1;

		// Iterate num from two to Min(X, Y)
		for (int num = 2; num < Math.min(x, y) + 1; num++) {
			// If X and Y are divisible by num
			if (x % num == 0 && y % num == 0) {
				ans = num;
			}
		}

		// Return the answer
		return ans;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(Min(X, Y))

    Space Complexity O(1)



    Where X and Y are the given integers.

*/



int findGcd(int x, int y)

{

    // Set initial answer as 1

    int ans = 1;



    // Iterate num from two to Min(X, Y)

    for(int num = 2; num < min(x, y) + 1; num++)

    {

        // If X and Y are divisible by num

        if(x % num == 0 && y % num == 0)

        {

            ans = num;

        }

    }



    // Return the answer

    return ans;

}

Python (3.5)

'''
    Time Complexity: O(Min(X, Y))
    Space Complexity O(1)

    Where X and Y are the given integers.
'''


def findGcd(x, y):

    # Set initial answer as 1
    ans = 1

    # Iterate num from two to Min(X, Y)
    for num in range(2, min(x, y) + 1):

        # If X and Y are divisible by num
        if(x % num == 0) and (y % num == 0):
            ans = num

    # Return the answer
    return ans

Accepted Answer

Euclidian Theoram

In this approach, we can use the Euclidian theorem that states the gcd of two numbers X and Y doesn’t change if we subtract the larger number from the smaller number. Therefore we can keep subtracting the smaller number from the larger number until the larger number is greater than, the smaller number.

Instead of repeatedly subtracting the number, we can use the modulo of the larger number with the smaller number and repeat the process until one of the numbers becomes 0, then we return the other number.

Therefore according to the Euclidian Theorem -:

gcd(X, Y) = gcd(Y, X % Y)
If X and Y are not equal 0.

We will create a recursive function findGcd(X, Y) that returns the greatest common divisor of the numbers X and Y.

Algorithm:

If Y is equal to 0, then return X. This will be the base case of the recursive function.
We will create a recursive call to find the gcd. We will return findGcd(Y, X % Y).

Space Complexity: OtherExplanation:

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

The space complexity O(log(Min(X, Y))) is required by the recursion stack in the worst case. Hence, the overall space complexity becomes O(log(Min(X, Y))).

Time Complexity: OtherExplanation: