# Editorial for XOR-Gun

Notice that if we can erase the sequence using more than $2$ operations then we can also erase it using $\le 2$ operations. Why? That’s because $x \oplus x \oplus x = x$. So we just have to check if the sequence can be erased using $1$ or $2$ operations.

If the XOR of elements of the whole sequence is $x$, then we can erase it using $1$ operations.

We can erase the sequence using exactly $2$ operations iff -

• $a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$

• There exists a non-empty subset of $a$ such that the XOR of the elements of that subsequence is $x$.

We can check the second condition in $\mathcal{O}(\log(2^{30}))$ using the basis vectors of the elements of $a$ and checking if $x$ is in the same subspace. Check this to know more.

So the problem can be solved in $\mathcal{O}(q \cdot 30)$.

Code(C++):

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

struct Basis {
vector<int> a;
void insert(int x) {
for (auto &i: a) x = min(x, x ^ i);
if (!x) return;
for (auto &i: a) if ((i ^ x) < i) i ^= x;
a.push_back(x);
sort(a.begin(), a.end());
}
bool can(int x) {
for (auto &i: a) x = min(x, x ^ i);
return !x;
}
}t;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
int tot = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
tot ^= x;
t.insert(x);
}
while (q--) {
int x; cin >> x;
if (tot == x) {
cout << 1 << '\n';
}
else if (tot == 0 and t.can(x)) {
cout << 2 << '\n';
}
else {
cout << -1 << '\n';
}
}
return 0;
}


### Statistics

75% Solution Ratio

NirjhorEarliest, 5M ago

LUMBERJACK_MANFastest, 0.1s

prodip_bsmrstuLightest, 1.0 MB

serotoninShortest, 571B 