2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I wonder if [0, 0, 0] and [0, 1, 1] are also solutions of your example. $\endgroup$ – Yoshio Okamoto Feb 3 '13 at 12:37
  • $\begingroup$ @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$. $\endgroup$ – Mahoni Feb 3 '13 at 12:40
  • $\begingroup$ @Mahoni: Following up on Yoshio's comment: why is $[2, 2, 0]$ not a solution? Similarly, why is $[3, 0, 3]$ not a solution? $\endgroup$ – Rachit Feb 3 '13 at 12:52
  • 4
    $\begingroup$ 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. $\endgroup$ – Jeffε Feb 3 '13 at 21:08
  • 2
    $\begingroup$ Can you solve the decision problem in (strongly) polynomial time? $\endgroup$ – Jeffε Feb 3 '13 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.