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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.