XOR subset with minimum length of the subset

Question

Array a has n integers.

Let l be the largest number in array a. Then, the expression for array a is ∑ⁿ_i=0 d_i ∗ 31ⁱ mod 10 ⁹ + 7 . Here, d_i

is the size of largest subset of array a whose XOR is equal to i.If there exist no subset of array i then d_i = 0 a whose XOR is i then d_i = 0.

Major concern is how to calculate subset with particular XOR in fastest time.

Answer 1

With $d:=10$, all $a_i$ numbers are $<2^{d}$, hence so are all possible XOR results. For $0\le i<2^{d}$ and $0\le j\le n$, let $f(i,j)$ denote the size of the largest subset of $\{a_1,\ldots, a_j\}$ that XORs to $i$. Then we have the recursion $$f(i,j)=\max\{f(i,j-1),1+ f(i\operatorname{xor} a_j,j-1)\}$$ with the initial condition $$ f(i,0)=\begin{cases}0&\text{if }i=0\\-\infty&\text{otherwise}\end{cases}$$ This allows us to compute $f(\cdot ,n)$ in $O(2^dn)$ steps. Here's some straightforward code to do so:

#define MODULUS 1000000007
#define PWR 1024  // 
#define NEGINFTY (-10001) // so that NEGINFTY+n < 0
int F[PWR];
unsigned n;
std::cin >> n;
for (int i=1; i<PWR; i++) F[i] = NEGINFTY;
F[0] = 0;
unsigned maxai = 0;
while (n-->0) {
  unsigned ai;
  std::cin >> ai;
  if (ai > maxai) maxai = ai;
  for (int i=0; i<PWR; i++) {
    unsigned ix = i ^ ai;
    if (i <= ix) {
      if (F[i] > F[ix])
        F[ix] = F[i]+1;
      else if (F[i] < F[ix])
        F[i] = F[ix]+1;
      else
        F[i] = ++F[ix];         
    }
  }
}
unsinged result = 0;
for (int i=maxi; i>=0; --i) {
  result = (result * 31) % MODULUS;
  if (F[i]>0) result = (result + F[i]) % MODULUS;
}
std::cout << result << std::endl;