# STONE05 - Editorial

Author: Vivek Kumar Mishra
Tester: Vivek Kumar Mishra
Editorialist: Prateek Chandra

HARD

Trees

# PROBLEM:

Find the largest set of correlative numbers

# EXPLANATION:

As we can see 1 \leq ans \leq n as the feasible range is clear we may use binary search to find out the answer.

# SOLUTIONS:

Setter's Solution

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

void findRem(vector &a,int n,int k,vector<vector> &r) {

for (int i = 0; i < n; i++) {
int rem = a[i] % k;
r[rem].push_back(a[i]);
}


}
bool isValid(vector &a,int n,int k,int m,vector<vector> &r){
for (int i = 0; i < k; i++) {
if(r[i].size() >= m) return true;
}
return false;
}

void solve(){
int n,k; cin>>n>>k;
vector a(n);
for(int i=0;i<n;i++) cin>>a[i];

vector<vector<int>> store_rem(k+1);
findRem(a,n,k,store_rem);


int l=1,r=1e6,ans=1;
while(l<=r){
int m=(l+r)>>1;
if(isValid(a,n,k,m,store_rem)){
ans=m; l=m+1;
}else r=m-1;
}
cout<<ans<<"\n";
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t–) solve();

}