PROBLEM LINK:
Author: Yash Dwivedi
Tester: Shubham Kushwaha
Editorialist: Nikhil Shukla
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
You are given an array of size n and you can choose any two indexes i and j and merge them together if a[i]*2 <= a[j] by merging I mean putting the smaller box into the bigger one. Thus, every merge operation will reduce the size of the array by one. You have to find out the minimum size you can get by doing this operation. Please note that you cannot choose any index more than once.
Observation:
Since you cannot choose one index more than one thus it means that the minimum number of elements you can have is ceil(n/2).
QUICK EXPLANATION:
First sort the array and then use two pointers technique, declare two-pointers one at the starting positions i.e at index 0, and the second at index ceil(n/2). Now choose the two index to merge if they satisfy a[first]*2 <= a[second] then increment number of mergeCount and increment both first and second and if they don’t just satisfy just increment the second pointer and do this till the second one reaches the end. The answer will be n-mergeCount.
EXPLANATION:
First of all, we can observe that we can have a minimum of ceil(n/2) elements or we can also say that we can perform a maximum of floor(n/2) merges. Now lets sort the array and declare two variables one pointing to the 0th index and the second pointing to ceil(n/2)th index. Now if the element at the first pointer satisfies the condition that a[first]*2 <= a[second] then it is optimal to choose elements at the first and second pointer and merge them but if the a[first]*2 > a[second] then as the array is sorted we can imply that a[first+i] > a[second] where 0 < first+i < second, so we just have to increment the second pointer we will do this until the second pointer reaches the end of the array. During every merge, we will keep track of mergeCount and the answer will be n-mergeCount.
Time complexity will be O(nlogn) as in every case we need to sort the given array.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n;
cin>>n;
ll i,a[n];
for(auto &i:a)
cin>>i;
ll mid=n/2;
ll grp=0;
ll total=n;
sort(a,a+n);
for(i=0;i<n/2;i++)
{
while(mid<n&&2*a[i]>a[mid])
{
mid=mid+1;
}
if(mid<n)
grp++;
mid++;
}
cout<<n-grp<<"\n";
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define endl "\n"
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
using namespace std;
void solve()
{
int n;
cin>>n;
vi a(n,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());
int ans=n,i=n-1,j=(n-1)/2;
while(j>=0)
{
if(2*a[j]<=a[i])
{
a[i]=a[j]=-1;
j--;
while(a[i]==-1){
i--;
}
ans--;
}
else
{
j--;
}
}
cout<<ans<<endl;
}
int main()
{
fast;
int t = 1;
while (t--)
{
solve();
}
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>g(n);
for(int i=0;i<n;i++)
{
cin>>g[i];
}
sort(g.begin(),g.end());
int f=0;
int s=ceil(n/2.0);
int cnt=0;
while(1)
{
if(s==n)
break;
if(g[f]*2<=g[s])
{
cnt++;
f++;
s++;
}
else
{
s++;
}
}
cout<<n-cnt<<"\n";
}
.