Problem Link

Author: @prasoonjain006

Tester: @prasoonjain006

Editorialist: @anshu8oct

Difficulty: Easy-Medium

Prerequisites : Number-theory, Euclid’s Gcd

**Problem description**

Chef has organized a party. He has Invited his N friends. Chef has made a special soft drink for the party. To serve it, he asked his friends to choose a glass of their preferred capacity. Each of the N friends have chosen a glass of capacity Ai liters.

Chef can serve the soft drink in one or more steps. In one step **chef can choose any Ai and serve exactly M liters of drink from his container into that chosen glass**. He can fill his container of M litre infinite number of times from that large tank. In one step, **1 unit of work is done**. In other words **work done in serving ith friend is Ai/M. Total work done W is work done in serving all of his N friends**.

There are some Conditions to choose the container of Size M :

- M should be less than each Ai, formally
**M≤Ai for 1≤i≤N** -
**Ai % M =0=0 ,1≤i≤N**.i.e. All Ai should be divisible M. - Total Work done
**W should be minimum possible**.

Can you find total minimum work done by Chef in serving all of the N friends ?

**Quick explanation**

From the conditions for M, it can be observed that **M has to divide every number in array and it should be the maximum number that divides for minimun W**. Hence, **gcd come into picture. It is calculated optimally by GCD Euclidean method**.

**Solution**

Setter’s solution

```
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> v(n);
int m=0,ans=0;
for(int i=0;i<n;i++)
{
cin>>v[i];
m=gcd(v[i],m);
}
for(int i=0;i<n;i++) ans+=(v[i]/m);
cout<<ans<<endl;
v.clear();
}
}
```

Time Complexity - O(nlogn)