Minimum Length Subsequence with XOR = 0

Revision en1, by ton, 2025-08-25 09:58:27

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ton 2025-08-25 09:59:04 0 (published)
en1 English ton 2025-08-25 09:58:27 786 Initial revision (saved to drafts)