ton's blog

By ton, history, 8 months ago, In English

Given an array of $$$n$$$ numbers $$${a_i}$$$ with $$$a_i \lt 2^{23}$$$, find the smallest $$$k$$$ such that there exist indices $$$0 \leq i_1 \lt \dots \lt i_k \leq n - 1$$$ for which $$$a_{i_1} \oplus \dots \oplus a_{i_k} = 0$$$.

I thought this was a well-known problem, but I couldn't find it. Maybe it can be solvable using Xor-Basis?(Or smth like meet-in-the-middle)

My dumbest solution is: If $$$\binom{n}{4} \gt 2^{23}$$$, then it is clear that an answer exists and has length $$$\leq 8$$$. It can be found in some sense by taking the $$$l$$$-th power of the Xor-Convolution(with $$$l \leq 8$$$)

Otherwise, $$$n \lt 120$$$, and we can write a solution in $$$O(n 2^m)$$$ using naive dp(Here $$$m = 23$$$)

I think there is definitely a solution that is much simpler and better than this.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it