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;
}