My issue
My code
#include <iostream>
#include<algorithm>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--){
int n,b;
cin>>n>>b;
int a[100000],c[100000];
for(int i=0;i<n;i++){
cin>>a[i];
}
int p=0;
int flag=0;
sort(a,a+n);
for(int i=0;i<n;i++){
if(b<=a[i])
break;
p++;
}
int k=0;
for(int i=p;i<n;i++){
if(a[i]&b==b)
c[k++]=a[i];
}
int d=c[0];
for(int i=0;i<k;i++){
d=d&c[i];
if(d==b)
flag=1;
}
if(flag==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Problem Link: CS2023_PON Problem - CodeChef
You can maintain a multiset of all integers in the beginning.
Now while iterating for each Bit in range [0, 31) you can encounter different cases according to different values of M. Let’s say you are checking for i’th Bit.
Case 1: ith bit = 0, in this case if all the integers in multiset have their ith bit = 1, then it’s never possible that their & = 0, hence you can directly return NO, otherwise if atleast one integers has ith bit set as 0 it will turn the & for that bit = 0, so no need to remove anything.
Case 2: ith bit = 1, in this case check for the same thing, if all ith bit of all integers is set to 0 then & of all the ith bit of all integers in the multiset will never be equal to 1, hence return NO, otherwise, if an element in the multiset has ith bit = 0, remove that element from the multiset.
In the end just check if (&) of all the elements in the multiset = M.
Here’s my way of implementing it: CodeChef: Practical coding for everyone