Linear dependences over the field with two elements The \$d\$-dimensional vector space \$\mathbb{F}_2^d\$ over the field with two elements \$\mathbb{F}_2\$ is the set of vectors of \$d\$ bits. Addition of vectors is bitwise xor. A linear dependence is a set of vectors whose total (xor them all together) is \$0\$. Every set of \$d+1\$ vectors in \$\mathbb{F}_2^d\$ contains a linear dependence. We will represent the elements of \$\mathbb{F}_2^d\$ as the integers \$0\$ through \$2^{d}-1\$ using the binary expansion.

Task

Input: a positive integer \$d\$ and a list of \$d+1\$ positive integers between \$1\$ and \$2^{d}-1\$. You may assume that the list is sorted and you may assume that the entries are distinct.

Output: A nonempty subset of the \$d+1\$ numbers whose bitwise xor is zero.

Scoring:

This is code golf so shortest answer in bytes wins.

Examples:

Input: (3, [1,3,4,7])
Output: [3, 4, 7]


In binary, these are 001, 011, 100, and 111. We see that 100 xor 011 xor 111 = 000. In this case this is the only solution, so we must output [3, 4, 7].

Test cases:

Input: (3, [1,3,4,7])
Output: [3, 4, 7]

Input: (4, [1, 2, 6, 10, 30])
Output: Behavior undetermined because 30 &gt; 15 = 2^4 - 1.

Input: (5, [3, 5, 6, 9, 14])
Output: [3, 5, 6]

Input: (5, [4, 8, 10, 12, 14])
Output: [4, 8, 12] or [4, 10, 14], or [8, 10, 12, 14].

Input: (6, [4, 15, 17, 21, 49, 51, 57])
Output: [4, 17, 21]

Input: (6, [1, 7, 8, 15, 39, 55, 57]) 
Output: [7, 8, 15] or [1, 15, 55, 57] or [1, 7, 8, 55, 57]

Input: (6, [13, 14, 24, 33, 35, 36, 63]) 
Output: [13, 14, 24, 36, 63]

Input: (6, [10, 11, 25, 28, 40, 59, 62])
Output: [10, 25, 40, 59] or [10, 28, 40, 62], or [25, 28, 59, 62]

Input: (6, [1, 3, 5, 11, 19, 32, 63])
Output: [1, 3, 5, 11, 19, 32, 63]
Jelly, 7 bytes

ŒPḊ^/ÞḢ


A monadic Link accepting the list of distinct integers representing the vectors which yields a subset representing the linear dependence. (May be employed as a dyadic Link also accepting the number of dimensions on the right.)

Try it online!

How?

ŒPḊ^/ÞḢ - Link: list of distinct integers   e.g. [1,3,4,7]
ŒP      - power-set                              [[],[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
  Ḋ     - dequeue                                [[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
     Þ  - sort by:
    /   -   reduce by:
   ^    -     XOR                              ( [1,3,4,7,2,5,6,7,4,3,6,5,2,0,1] )
        - }                                      [[3,4,7],[1],[1,3,4,7],[1,3],[1,4,7],[3],[4,7],[4],[3,7],[1,4],[1,3,7],[1,7],[1,3,4],7,[3,4]]
      Ḣ - head                                   [3,4,7]