# Doubt for bench press quesion

this is the ques

I am getting TLE

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

int main()
{
int t,n,w,wr,i,p,ans,tot,j,c;

cin>>t;
while(t–)
{
w=0;tot=0;
cin>>n >> w >> wr;
int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
//logic…
if(wr>=w)
cout<<“YES”<<endl;
else

``````{
sort(arr,arr+n);

i=0;
while(i<n)
{
j=i+1;
while(j<n)
{
if(arr[i]!=arr[j])
break;
j++;
c++;
if(c>1)
{
tot=tot+c*arr[i];
if(c%2==1)
tot=tot-arr[i];
if(tot>=w)
break;
}
i=j;
}
if(tot>=w)
cout<<"YES"<<endl;
else
cout<<"YES"<<endl;
}
}
}
return 0;
``````

}

why you are using two loops in here, instead it can be solved easily using 1 while loop only.
You have already sorted the array, then just compare 2 elements at a time if those two elements are equal then add that weight and increase counter by 2, if elements are not equal then just increase the counter by 1 and don’t add that weight to the ans.

N can go upto 10^5, so O(N^2) time complexity will definitely give TLE. Think of O(NlogN) or O(N) approach.
A easy to think O(N) approach is to use unordered_map and store frequency of each element, then just add el*(freq[el]/2)*2 to answer for each element. I will go with map because of trust issues with unordered_map and time complexity will be O(NlogN), still affordable.

Try Reducing Loops It Will Work @anon74541909

You’re literally spamming everywhere and begging for likes.

2 Likes