<p>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:</p>

<ol>
<li>$x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.</li>
<li>$x_k \in [0,a_k]$ for each $k$.</li>
<li>$x_k=a_k$ for at least one $k$.</li>
</ol>

<p>For instance, if the given list is <code>[1,2,3]</code>, the answer is 4, and the specific solutions are</p>

<ul>
<li><code>[0,2,2]</code>,</li>
<li><code>[1,0,1]</code>,</li>
<li><code>[1,1,0]</code>, and</li>
<li><code>[1,2,3]</code>.</li>
</ul>

<p>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 <code>[0,0,0]</code>. 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</p>

<p>$$E[n,i]$$</p>

<p>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:</p>

<p>$$
\begin{align*}
  E[0,0] &amp; = 0 \\
  E[0,i] &amp; = 1 + m_i \\
  E[n,i] &amp; = (1 + m_i) \cdot E[n, i-1] \\
  E[n,i] &amp; = \text{invalid if } i + 1 &gt; n
\end{align*}
$$</p>

<p>But how can I integrate the XOR constraint here?</p>

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

CC BY-SA 3.0
2013-02-03T12:37:19.120Z
I wonder if [0, 0, 0] and [0, 1, 1] are also solutions of your example.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-03T12:40:42.147Z
@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
CC BY-SA 3.0
2013-02-03T12:52:05.157Z
@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
CC BY-SA 3.0
2013-02-03T12:55:17.373Z
@Rachit Because the first integer cannot be bigger than $1$. The input defines for each slot the cap of the numbers.
Mahoni
CC BY-SA 3.0
2013-02-03T13:05:45.020Z
@Mahoni: Thank you for the clarification.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-03T21:08:26.597Z
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ε
CC BY-SA 3.0
2013-02-03T21:09:26.453Z
Can you solve the decision problem in (strongly) polynomial time?
Jeffε
CC BY-SA 3.0
2013-02-05T13:22:56.503Z
@JɛﬀE: Interestingly, it's easy to see that even the counting version is in $P$ if each $a_k$ is of the form $2^{b_k}-1$; then the problem reduces to counting solutions to linear equations over GF(2). (Condition 3 is easily handled by fixing one variable $x_k$ and solving $k$ different subproblems). 
The problem is how to deal with initial all-ones segments of $a_1,\ldots,a_k$ (followed by zero). We could attempt to iterate over the lengths of these segments, but this leads to an $O(\rm{poly}(k) \cdot \prod_k \log a_k)$-time algorithm.
david
<co.combinatorics><gt.game-theory><dynamic-programming><ds.algorithms>
How can I find all numbers for which the XOR-sum is 0?
Mahoni
# How can I find all numbers for which the XOR-sum is 0?

(Asked by: username_0 on 2013-02-03)

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.

**Tags:** co.combinatorics, gt.game-theory, dynamic-programming, ds.algorithms

> **Comments:**
> **username_1**: I wonder if [0, 0, 0] and [0, 1, 1] are also solutions of your example.  
> **username_0**: @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$.  
> **username_2**: @username_0: Following up on Yoshio's comment: why is $[2, 2, 0]$ not a solution? Similarly, why is $[3, 0, 3]$ not a solution?  
> **username_0**: @username_2 Because the first integer cannot be bigger than $1$. The input defines for each slot the cap of the numbers.  
> **username_1**: @username_0: Thank you for the clarification.  
> **username_3**: 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.  
> **username_3**: Can you solve the decision problem in (strongly) polynomial time?  
> **username_4**: @JɛﬀE: Interestingly, it's easy to see that even the counting version is in $P$ if each $a_k$ is of the form $2^{b_k}-1$; then the problem reduces to counting solutions to linear equations over GF(2). (Condition 3 is easily handled by fixing one variable $x_k$ and solving $k$ different subproblems).  The problem is how to deal with initial all-ones segments of $a_1,\ldots,a_k$ (followed by zero). We could attempt to iterate over the lengths of these segments, but this leads to an $O(\rm{poly}(k) \cdot \prod_k \log a_k)$-time algorithm.  

---

## 0 answers

