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

Comments

Popular posts from this blog

problem 3: given two integers N and M. The problem is to find the number closest to N and divisible by M. If there are more than one such number, then output the one having maximum absolute value.

problem no 7:Given two numbers A and B, find Kth digit from right of AB.

Problem no 16: count the number of squares below N.