Abhishek

D.

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

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

//--- Precompute the first ~440k primes by sieving up to 7e6 ---
const int SIEVE_MAX = 7'000'000;
vector<bool> is_prime(SIEVE_MAX+1, true);
is_prime[0] = is_prime[1] = false;
for(int i = 2; i*i <= SIEVE_MAX; i++){
if(is_prime[i]){
for(int j = i*i; j <= SIEVE_MAX; j += i)
is_prime[j] = false;
}
}
// collect primes and build their prefix sums P_k = sum of first k primes
vector<ll> P;
P.reserve(450000);
ll running = 0;
for(int i = 2; i <= SIEVE_MAX; i++){
if(is_prime[i]){
running += i;
P.push_back(running);
if((int)P.size() >= 440000)
break;
}
}
// P[k-1] = sum of first k primes

int t;
cin >> t;
while(t--){
int n;
cin >> n;

vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}

// sort descending and build prefix sums S_k
sort(a.begin(), a.end(), greater<>());
vector<ll> S(n+1, 0);
for(int i = 0; i < n; i++){
S[i+1] = S[i] + a[i];
}

// find largest k in [0..n] with S[k] >= P[k-1]
// (for k=0, P[-1] interpreted as 0)
int best_k = 0;
for(int k = 1; k <= n; k++){
if(k > (int)P.size()) break; // no more primes precomputed
if(S[k] >= P[k-1])
best_k = k;
else
break;
}

// We must remove (n - best_k) to leave best_k “beautiful” elements
cout << (n - best_k) << "\n";
}

return 0;
}

1 week ago | [YT] | 0