# PROBLEM LINK:

Practice

* Tester:* Aman Nautiyal

*Aman Nautiyal*

**Editorialist:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Binary search on answer, Math.

# PROBLEM:

Ayush’s family and a few other families want to go to a haunted house together. They have to enter the haunted house in a single queue. Ayush is a miser and he wants to maximize the fear of every person by making sure that they are as far as possible from their family members in the queue. Every person in the family has a similar code represented with integers.

Ayush is busy packing his bag so he asks you to help him to calculate the greatest minimum distance between the same family member amongst all possible orders of queue.

# EXPLANATION:

Let’s note that if you can find the arrangement with the maximum distance of x then you can also find the maximum distance of x-1. It allows you to use the binary search on the answer.

# SOLUTIONS:

## Setter's Solution

#include<bits/stdc++.h>

```
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
void solve()
{
int n,i,person,ans=0,j;
cin>>n;
vector<int> family(n+1),vis(n);
for(int i=0;i<n;i++)
{
cin>>person;
family[person]++;//storing the number of persons belong to same family (same family code)
}
sort(family.begin(),family.end());
reverse(family.begin(),family.end());//start fixing the order from largest family to smallest
int l=0,r=n-2; //maximum possible distance is at most n-2
while(l<=r)
{
int mid=(l+r)/2;
bool f=true;
for( i=0;i<n;i++)vis[i]=0;//all positions are available
for(i=0;i<n;i++)
{
if(vis[i]) continue; // if person is present at index i
for(j=0;j<family[i] && f;j++)
{
int nextpos=i+(mid+1)*j;
if(nextpos>=n) f=false;//not possible to maintain mid(units) of distance
else vis[nextpos]=1;
}
if(!f)break;
}
if(f) ans=max(ans,mid),l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
}
int main()
{
IOS;
int T=1;
cin>>T;
for(int t=1;t<=T;t++)
{
solve();
}
return 0;
}
```