# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* himanshu154

*jay_1048576*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Familiarity with bitwise AND

# PROBLEM:

Given an array A and an integer B, does there exist a subsequence of A whose bitwise AND equals B?

# EXPLANATION:

First, recall the following property of bitwise AND:

That is, if x\ \&\ y = z, then both x and y will be *supermasks* of z (meaning any bit set in z will also be set in x and y).

This of course extends to the bitwise AND of several values as well:

If x_1 \ \&\ x_2\ \&\ \ldots \ \&\ x_k = y, then each x_i will be a supermask of y.

Let’s look at the above property from the perspective of the problem we want to solve.

We want to figure out whether there’s a subsequence of A such that its bitwise AND equals B.

That is, we want to know whether there exist indices 1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq N such that

Immediately, the first property tells us that each A_{i_j} will be a supermask of B.

So, we only care about those values in A that are supermasks of B.

Let S be the set of values in A that are supermasks of B.

Then, in fact S is the subsequence we’re looking for!

That is, if the bitwise AND of the values in S equals B, the answer is `Yes`

.

Otherwise, the answer is `No`

.

## Why?

If the bitwise AND of S equals B, obviously the answer is `Yes`

since we directly found a valid subsequence.

Now, suppose the bitwise AND of S doesn’t equal B.

Since every element of S has B as a submask, clearly their AND must also have B as a submask.

However, since it doesn’t equal B, the AND must also be a strict supermask of B — that is, there exists some bit k such that B doesn’t have k set; but every element of S does have k set.

Now, consider an arbitrary subsequence of A.

- If this subsequence includes an element outside S, clearly its bitwise AND cannot be B (by definition of S).
- If this subsequence is fully contained in S, then its AND will have bit k set for sure; and so cannot equal B anyway.

So, no subsequence has a bitwise AND of B, as claimed.

This gives a simple linear solution: find the bitwise AND of all supermasks of B, and check if it equals B or not.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

## Setter's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define rep(i,a,b) for(int i=a;i<b;i++)
void solve(){
int n,b;
cin>>n>>b;
vector<int> arr(n);
rep(i,0,n) cin>>arr[i];
int res_and=(1LL<<31)-1;
int cnt=0;
rep(i,0,n){
if((arr[i]&b) == b){
res_and = res_and & arr[i];
cnt++;
}
}
if(res_and == b && cnt>0){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("D:/Desktop/Test_CPP/CS2023_PON/CS2023_PON_3.in", "r", stdin);
freopen("D:/Desktop/Test_CPP/CS2023_PON/CS2023_PON_3.out", "w", stdout);
#endif
int t=1;
cin>>t;
while(t--){
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-6 << "ms\n";
return 0;
}
```

## Tester's code (C++)

```
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
void solve(int tc)
{
int n,b;
cin >> n >> b;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
int c = INT_MAX;
for(int i=0;i<n;i++)
{
if((a[i]|b)==a[i])
c &= a[i];
}
if(c==b)
cout << "YES\n";
else
cout << "NO\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, b = map(int, input().split())
have = 2**31 - 1
for x in list(map(int, input().split())):
if x&b == b: have &= x
print('Yes' if have == b else 'No')
```