Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
4  
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. –  JɛffE Feb 3 '13 at 21:08
2  
Can you solve the decision problem in (strongly) polynomial time? –  JɛffE Feb 3 '13 at 21:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.