CH2B editorial

editorial
,
1

PROBLEM LINK:

Practice

Contest

Author: Rishabh Jain

Tester: Chandan Boruah

Editorialist: Rishabh Jain

DIFFICULTY:

EASY

PREREQUISITES:

Basic Maths (GCD)

PROBLEM:

Given an array where the number of dishes are given, find the maximum number such that all the array elements are divisibe by it.

QUICK EXPLANATION:

The number would be the gcd(array).

EXPLANATION:

Basically when we want each student to get the same combination of dishes, we want that each teacher’s dish must be equally distributable. We do not want to waste, hence the ans must be perfectly divisibe by all the array elements. Therefore the answer would be the greatest common divisor (or Highest Common Factor) of the whole array.

AUTHOR’S SOLUTION IN CPP

#include<bits/stdc++.h>
	#define ll long long
	using namespace std;


	ll a[50];
	ll ans;
	int main()
	{
		ll t,n;
		cin>>t;
		while(t--)
		{
			cin>>n;
			for(int i=0;i<n;i++)
				{
					cin>>a[i];
					ans = a[0];
					ans = __gcd(ans, a[i]);
				}

			cout<<ans<<"\n";
		}


		return 0;
	}