My issue
what is wrong in this approach
My code
#include <bits/stdc++.h>
using namespace std;
#define long long int
vector<int> arr;
bool isPossible(int h, int n, int k){
//cout<<"at isPossible "<<h<<endl;
priority_queue<int> extras, defs;
int hCount = 0;
for(int i: arr){
if(i>=h) hCount++;
else{
if(i%k!=0) defs.push(i);
}
if(i%k==0 and i/k>=h) extras.push(i);
}
if(hCount>=h) return true;
if(defs.empty() or extras.empty()) return false;
while(!defs.empty() and !extras.empty()){
int tar = defs.top(); defs.pop();
int donar = extras.top();
extras.pop();
//cout<<"cur donar = "<<donar<<" and tar = "<<tar<<endl;
donar/=k;
tar *= k;
if(tar>=h) hCount++;
else break;
if(hCount>=h) return true;
if(donar%k==0 and donar/k>=h) extras.push(donar);
}
return hCount>=h;
}
signed main() {
int t; cin>>t;
while(t--){
int n, k;
cin>>n>>k;
arr = vector<int>(n);
for(int i=0; i<n; i++)
cin>>arr[i];
int left = 1, right = n;
int ans = left;
while(left<=right){
int cur = left + (right-left)/2;
if(isPossible(cur, n, k)){
ans = max(ans, cur);
left = cur+1;
}
else right = cur-1;
}
cout<<ans<<endl;
}
}
Problem Link: Array Operations Practice Coding Problem - CodeChef