Minimum number of moves to make all elements of the sequence zero.

Question

Given $N$ numbers $a_1, a_2, ..., a_n$ I want to make $a_1 = a_2 = ... = a_n = 0$ by using minimum number of operations. An operation is taking any two numbers $a_i$ and $a_j$ ($i$ may be equal to $j$) and calculating $a_i$ xor $a_j$ and replacing $a_i$ with it and replacing $a_j$ with it. How to calculate minimum number of operations required to make all numbers in the sequecne $0$? XOR is defined to be bitwise xor.

Answer 1

Claim : There is a sequence of minimal length where every XOR operation is done between two equal numbers.

Proof : Consider a sequence of operation with minimal length, and let $(i,j)$ be the last operation between two distinct numbers $x_i\neq x_j$. After this operation, registers $r_i$ and $r_j$ will contain number $x_i\oplus x_j$. Because $x_i\neq x_j$ necessarily $x_i\oplus x_j\neq 0$, so there exist one or two more operations $(i,k)$ and $(j,l)$ after $(i,j)$. There are three cases depending on whether $l,k\in\{i,j\}$.

• Both $l,k\in\{i,j\}$, there is only one more operation which is again $(i,j)$. Instead of doing $(i,j)$ twice, we can do $(i,i)$ and $(j,j)$.
• $k\notin\{i,j\}$ and $l\in\{i,j\}$. We necessarily have $l=j$. Registers $r_i,r_j,r_k$ are set to zero by the three operations $(i,j)$, $(i,k)$ and $(j,j)$. Those can be replaced by $(i,i)$, $(j,j)$ and $(k,k)$.
• Both $l,k\notin\{i,j\}$. Because $(i,l)$ and $(j,k)$ must set all four registers $r_i,r_j,r_k,r_l$ to zero, we deduce that registers $r_k$ and $r_l$ must contain number $x_i\oplus x_j$. It follows that we can also set those four registers to zero with the series of operations $(i,i)$, $(j,j)$ and $(k,l)$.

It follows that we can remove every operation between distinct numbers, and that there exists a sequence of minimum length with only operations between equal numbers.

---

Suppose you have $k$ distinct numbers $a_1,\ldots,a_k$ with multiplicity $m_1,\ldots,m_k$, $\sum_{i=1}^k m_i=n$. Then the length of the minimal sequence is $$\text{opt}=\sum_{i=1}^k\left\lceil \frac{m_i}2 \right\rceil$$