Problem link: CodeChef: Practical coding for everyone
Difficulty: Easy
Explanation: For each x from 1 to 5000 calculate count(x) — the number of measurements equal to
x.
The iterate over all possible minimal values m (from 1 to 5000).
For a fixed m we can easily figure out which numbers we have to erase: we should
erase every number k that k < m or k > 2·m.
To find out the number of such values in the given sequence, we should sum up
values count(k) for all such k.
Alternate way : We can easily get the answer by just applying binary search in the
given array.
Code:
#include<bits/stdc++.h>
using namespace std;
int n,x,a[100005],ans=INT_MAX;
int main() {
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++) {
x=upper_bound(a,a+n,a[i]*2)-a;
ans=min(ans,i+n-x);
}
cout<<ans<<endl;
return 0;
}