Question

iven 2 non-negative integers m and n, find gcd(m, n)
GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n. Both m and n fit in a 32 bit signed integer.

NOTE: DO NOT USE LIBRARY FUNCTIONS
Input
Input contains two space separated integers, m and n

Constraints:-
1 < = m, n < = 10^18
Output
Output the single integer denoting the gcd of the above integers.

Answer 1

Explanation:

Given 2 non negative integers m and n, find gcd(m, n) GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n. Both m and n fit in a 32 bit signed integer. Example m : 6 n : 9 GCD(m, n) : 3 NOTE : DO NOT USE LIBRARY FUNCTIONS Tags: InterviewBit Mathint Solution::gcd(int A, int B) {

//Euclid's algorithm

while(B!=0)

{

int r = A%B;

A = B;

B = r;

}

return A;

}

//Recursive one line solution

/*int Solution::gcd(int A, int B) {

//Euclid's algorithm

return B==0 ? A : gcd(B, A%B);

}*/