#include
#include
#include<math.h>
using namespace std;
long long countbits(long long d)
{long long cnt=0;
while(d!=0)
{
d=d/2;
cnt++;
}
return cnt;
}
long long checkforkbits(long long e,long long k)
{
long long cnt1=0;
while(e!=0)
{
if(e%2!=0)
{
cnt1++;
}
e=e/2;
}
if(cnt1==k)
return 1;
else
return 0;
}
int main()
{
long long t;
cin>>t;
while(t–)
{
long long n,g,k,sum=0,ans=0,b;
long long i,a[100];
cin>>n>>k;
for(i=0;i<n;i++)
cin>>a[i];
g=*max_element(a,a+n);
long long z=countbits(g);
long long r=pow(2,z);
for(long long j=0;j<r;j++)
{
long long d=checkforkbits(j,k);
if(d==1)
{ long long cur=ans;
sum=0;
for(i=0;i<n;i++)
{int f=a[i]&j;
sum=sum+f;
}
ans=max(ans,sum);
if(ans>cur)
{
b=j;
}
}
}
cout<<b<<endl;
}
}
what’s the wrong with my code it’s showing TLE
It is difficult to read, please send the link or the formatted code. People tend to ignore posts with non-formatted code.
I think the problem in the line
while(t-) {...}
If it doesn’t help, you can take help of my solution
I will give you a basic idea.
We have to greedily choose those bit position for which total contribution in the answer is maximum
Hope it helps.
Cheers.
#include
#include
#include<math.h>
using namespace std;
long long countbits(long long d)//count number of bits of a number
{long long cnt=0;
while(d!=0)
{
d=d/2;
cnt++;
}
return cnt;// return total number bits in binary form
}
long long checkforkbits(long long e,long long k)// this function check that value ‘e’ has exactly k bits equal to 1 or not
{
long long cnt1=0;
while(e!=0)
{
if(e%2!=0)
{
cnt1++;
}
e=e/2;
}
if(cnt1==k)
return 1;// if number has exactly k bits in binary reprsentation is equal to 1
else
return 0; // if number does not has n exactly k bits in binary reprsentation is equal to 1
}
int main()
{
long long t;// number of test cases
cin>>t;
while(t–)
{
long long n,g,k,sum=0,ans=0,b;
long long i,a[100];
cin>>n>>k;// toatl number in arry
for(i=0;i<n;i++)
cin>>a[i];
g=max_element(a,a+n);
long long z=countbits(g);// z store the number of bits of maximum of the array
long long r=pow(2,z);/ r store the value till which we get the x and after that r value we get 0 because there will be increment in bits by 1 example if maximum of array is 5 then number
of bits in 5 is 3 then 2^3=8 then we will find the x till 8 becuse from one bit will increment i.e 1000 and 5=101 so and of any elememt of arry with greater than 8 will be zero*/
for(long long j=0;j<r;j++)// this loop will work till 2^(number of bits in binary reprsentation present in the array)
{
long long d=checkforkbits(j,k);// we check that j value has eaxtly k bits equal to 1 in binary reprsentation
if(d==1)// that j value has exacctly k bits equal to 1 in binay reprsentation
{ long long cur=ans;// store previous value of ans
sum=0;
for(i=0;i<n;i++)
{int f=a[i]&j;// and the x i.e j with a[i]
sum=sum+f;//sum the result of and function with x and a[i]
}
ans=max(ans,sum);// find max of the ans for x avlue
if(ans>cur)// if previous vlaue of ans which sotre in cur is less than the new value the we store that x value in b for which we get maximum sum
{
b=j;
}
}
}
cout<<b<<endl;
}
}