Problem no 11: GCD of the entire array.

QUESTION:

GCD of Array


Given an array of N positive integers, find GCD of all the array elements.


Example 1:

Input: N = 3, arr[] = {2, 4, 6}
Output: 2
Explanation: GCD of 2,4,6 is 2.


Example 2:

Input: N = 1, arr[] = {1}
Output: 1
Explanation: Greatest common divisor of
all the numbers is 1.


ANSWER:

  
    int gcd(int N, int arr[])
    {
        if(N==1)
        {
            return arr[0];
        }
        else
        {
               int result=gcdd(arr[0],arr[1]);   .....calling gcdd function
        for(int i=2;i<N;i++)
        {
            result=gcdd(result,arr[i]);            .....calling gcdd function
        }
        return result;
        }
   
    }

 

  int gcdd(int a, int b)
    {
       int res = 0;
      while (b > 0){
         int temp = b;
         b = a % b;
         a = temp;
         res = a;
      }
      return res;
    }           
    

 

 

 

want to know more about gcd?

click here.


 

 

 

 

 

 

 

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.