# How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied:

1. $x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.
2. $x_k \in [0,a_k]$ for each $k$.
3. $x_k=a_k$ for at least one $k$.

For instance, if the given list is [1,2,3], the answer is 4, and the specific solutions are

• [0,2,2],
• [1,0,1],
• [1,1,0], and
• [1,2,3].

A brute-force approach would just compute the Cartesian product of all $x_k$s or simply count through the whole number space starting with [0,0,0]. But how can I tackle this problem with a more sophisticated algorithm? What paradigm is a good choice? Dynamic programming? If I only consider condition 2, then I could think of denoting the sub-problem by

$$E[n,i]$$

Where $n$ defines the number of integers and $i$ the current slot. Also given the caps $[m_1, m_2, \dots,m_n]$ then the number of combinations could be computed with:

\begin{align*} E[0,0] & = 0 \\ E[0,i] & = 1 + m_i \\ E[n,i] & = (1 + m_i) \cdot E[n, i-1] \\ E[n,i] & = \text{invalid if } i + 1 > n \end{align*}

But how can I integrate the XOR constraint here?

On the other hand it seems this is a classical Constraint Satisfaction Problem which could be backtracked.

• I wonder if [0, 0, 0] and [0, 1, 1] are also solutions of your example. – Yoshio Okamoto Feb 3 '13 at 12:37
• @YoshioOkamoto No, sorry for making a false impression. But look at the last paragraph starting with Another constraint. [0, 0, 0] and [0, 1, 1], both, do not have one number slot, which was kept untouched. There is no $x_k$ in it, which sill has the original value $a_k$. – Mahoni Feb 3 '13 at 12:40
• @Mahoni: Following up on Yoshio's comment: why is $[2, 2, 0]$ not a solution? Similarly, why is $[3, 0, 3]$ not a solution? – Rachit Feb 3 '13 at 12:52
• This is easy to solve by dynamic programming in $O(n A^2)$ time, where $A = \max_i a_i$. Let $F(j, t)$ denote the number of tuples $(x_1, x_2, \dots, x_j)$ where (1) $0\le x_i \le a_i$ for every index $i\le j$, (2) $x_i = a_i$ for some index $i\le j$, and (3) $x_1\oplus x_2\oplus\cdots\oplus x_j = t$. There are $O(nA)$ subproblems, each of which can be evaluated in $O(A)$ time. – Jeffε Feb 3 '13 at 21:08
• Can you solve the decision problem in (strongly) polynomial time? – Jeffε Feb 3 '13 at 21:09