problem no 9: GCD of A and B.
QUESTION:
Given two positive integers A and B, find GCD of A and B.
Example 1:
Input: A = 3, B = 6
Output: 3
Explanation: GCD of 3 and 6 is 3
Example 2:
Input: A = 1, B = 1
Output: 1
Explanation: GCD of 1 and 1 is 1
Inefficient code for gcd:
int gcd(int A, int B)
{
int small;
if(A>B)
{
small=B;
}
else
{
small=A;
}
for(int i=small;i>=0;i--)
{
if(A%i==0 && B%i==0)
{
return i;
}
}
return -1;
}
Efficient code:
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
Comments
Post a Comment