problem no 9: GCD of A and B.

 

 

 

 

 QUESTION:

 

GCD of two numbers

---

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);
          
    }