We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} ( A_i \text { xor } A_j )^X$. $X$ is either 2 or 3. $N$ can be up to $50000$.

I know that this can be solved in $O(N^2)$ but I was wondering if we can fast this calculation since this is pretty slow for big values of $N$. Are there any properties of xor that can be used to speed up calculations.

  • $\begingroup$ Is $X$ the same for all terms $(A_i\ \mathrm{xor}\ A_j)^X$? $\endgroup$ – xskxzr Dec 2 '18 at 4:30
  • $\begingroup$ Yes, x is same for all pairs $\endgroup$ – someone12321 Dec 2 '18 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.