GCD (HCF) of N Integers
N integers are passed as input to the program. The program must print the GCD (HCF) of these N integers.
Input Format:
The first line contains N.
The second line contains N integers each separated by a space.
The first line contains N.
The second line contains N integers each separated by a space.
Output Format:
The first line contains the HCF of these N numbers.
The first line contains the HCF of these N numbers.
Boundary Conditions:
2 <= N <= 100
2 <= N <= 100
Example Input/Output 1:
Input:
4
15 20 30 50
Input:
4
15 20 30 50
Output:
5
5
Code:
#include
<iostream>
using
namespace std;
int
gcd(int a, int b)
{
if(a==0)
return b;
return gcd(b%a,a);
}
int
main(int argc, char** argv)
{
int
n,i;
cin>>n;
int
arr[n];
cin>>arr[0];
int
res=arr[0];
for(i=1;i<n;i++)
{
cin>>arr[i];
res=gcd(arr[i],res);
}
cout<<res;
}
Please do comment If u have any Queries!
Why did you assign int res=arr[0];? Please explain me.
ReplyDeleteThe GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.
ReplyDeletegcd(a, b, c) = gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
For an array of elements, we do following.
result = arr[0]
For i = 1 to n-1
result = GCD(result, arr[i])