CHFPRTY Editorial

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)

1 Like