# PROBLEM LINK:

**Setter:** Razaul Hasan Ansari

**Tester:** Nitin Pundir

**Editorialist:** Rishav Sharma

# DIFFICULTY

Easy

# PREREQUISITES

Observation.

# PROBLEM

Razaul is having a new year party at his home. There are a total of N people in the party(including himself). He decided to pour cocktails for everyone. The i-th glass has ai amount of cocktail(the amount of cocktail is measured in whole numbers Eg. 1,2,13986 ..). He then remembered that he doesn’t drink so he took one of the glasses at random and divided all of its contents among the rest of the N−1 glasses.

Razaul wants that after doing so all the glasses must have an equal amount of cocktail. You decided to help and poured a total X amount of extra cocktail into the glasses(can be one or many) so as when he divides the contents of one of the random glasses all the glasses have equal amount.

What is the value of X ?

# OBSERVATION

The task here to Razaul is to empty the ith drink he’s chosen and wants all the other N-1 drinks to contain equal amounts of cocktail. That means, that the sum of the array must be divisible by (n-1) and the amount of cocktail in each glass must be ceil(sum/n-1).

On the other side, since Razaul chooses the glass at random, then he can choose a glass which is NOT the maximum, and since he empties it, then the final amount in each glass must at least be max.

In total, the resulting number of cocktail, in each of the glass(except the chosen one) must at least be q = max(ceil(sum/n-1), maxx), where maxx = maximum element in the array. And, we need to add at least (n-1)*q - sum elements to the initial array.

# TIME COMPLEXITY

The time complexity is O(N) as we traverse the array one time to find the maximum of the array.

# SOLUTION

## Setter's Solution

```
```#include<bits/stdc++.h>

`using namespace std;`

using ll=long long;

int main()

{

int t;

cin>>t;

while(t–)

{

ll sum=0,mx=0,n;

cin>>n;

for(int i=0;i<n;i++)

{

ll k;

cin>>k;

mx=max(mx,k);

sum+=k;

}

ll c = ceil((sum*1.0)/(n-1));
ll need=max(mx,c);
cout<<need*(n-1)-sum<<endl;

}

}

## Tester's Solution

```
#include "bits/stdc++.h"
```#define ll long long

using namespace std;

ll md=1000000007;

ll diff=-1;

string mins;

`int main()`

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

ll t;

cin>>t;

while(t–)

{

ll n;

cin>>n;

vector arr(n);

ll sum=0;

ll maxi=-1;

for(int i=0;i<n;i++)

{

cin>>arr[i];

sum+=arr[i];

maxi=max(maxi,arr[i]);

}

ll tr=maxi*(n-1);

if(tr>=sum)

cout<<tr-sum<<endl;

else

{

if((sum-tr)%(n-1)==0)

cout<<0<<endl;

else

cout<<(n-1-(sum-tr)%(n-1))<<endl;

}

}

return 0;

}