In this post I’m going to prove some results needed to solve the “XOR-sequence” HackerRank problem found here.
Spoiler warning for anyone who wants to solve the problem first.
For two natural numbers $x$ and $y$ I will denote $\text{XOR}(x, y)$ as $x\oplus y$. I’m considering an array, denoted $A$, where $A_0 = 0$ and for $x > 0$
$$
A_x = x\oplus A_{x-1} \\
= x\oplus(x-1)\oplus A_{x-2} \\
= \bigoplus_{k=0}^x k
$$
so this is like an XOR factorial. The actual problem requires finding a fast way to evaluate
$$
\bigoplus_{x=\ell}^r A_x
$$
for potentially huge $\ell$ and $r$.
I’ll begin by proving the following:
Result 1: $(\mathbb N, \oplus)$ is an abelian group and every non-identity element has order 2 (making it a Boolean group).
Pf: The key idea behind most of these results is that for two numbers $x,y\in \mathbb N$, $x \oplus y$ is determined by considering each bit of their binary expansions separately (with $0$-padding as needed) so much of this only needs to be shown for individual bits, not arbitrary numbers.
1. Closure: $x \oplus y$ yields a binary number which is necessarily an element of $\mathbb N$.
2. Associativity: A truth table shows that $\oplus$ is associative for single bits (i.e. $x,y,z\in \{0,1\}$). Applying element-wise means $\oplus$ is associative in general.
3. Commutativity: by definition $\oplus$ is commutative on single bits so the result follows.
4. Existence of identity: let $x \in \{0,1\}$ and consider $x \oplus 0$. $1\oplus 0 = 1$ and $0\oplus 0 = 0$ so $x \oplus 0 = x$ no matter what $x$ is. Applying this element-wise means $x\oplus 0 = 0\oplus x = x$ for any $x\in\mathbb N$.
5. Inverses exist: for any $x \in \mathbb N$ $x\oplus x = 0$. This also shows that every non-zero element has order $2$.
$\square$
I can use these properties to simplify the problem. I don’t want to make special cases for $\ell = 0$ so I’ll define $\bigoplus_{x=0}^{-1} A_x = 0$. Noting then that everything commutes and $\bigoplus_{x=0}^{\ell-1} A_x$ is simply some element of $(\mathbb N, \oplus)$, and therefore has order $2$, I have
$$
\bigoplus_{x=\ell}^r A_x = \left(\bigoplus_{x=0}^r A_x\right) \oplus \left(\bigoplus_{x=0}^{\ell-1} A_x\right)
$$
so I merely need to find a good description for these products and I’m done.
To that end, let
$$
F(y) = \bigoplus_{x=0}^y A_x
$$
so
$$
\bigoplus_{x=\ell}^r A_x = F(r)\oplus F(\ell – 1)
$$
(by my definition for $\ell =0$ I have $F(-1) = 0$ which reflects that if $\ell =0$ $F(r)$ is the entire problem).
Consider now
$$
\bigoplus_{x=8n}^{x=8n+7} A_x
$$
for some $n \in \mathbb N$. Using the fact that $A_{y + 1} = (y+1)\oplus A_y$, so $A_y \oplus A_{y+1} = y+1$, I have
$$
\bigoplus_{x=8n}^{x=8n+7} A_x = (8n + 1)\oplus (8n+3) \oplus (8n + 5) \oplus (8n + 7).
$$
The following lemma will now help.
Lemma 1: for $x\in\mathbb N$, if $2^m \vert x$ then the binary expansion of $x$ ends in at least $m$ $0$s.
Pf: let
$$
x = \sum_{k=0}^n a_k2^k
$$
be the binary expansion of $x$. It must be that $m \leq n$ since otherwise $2^m > x$ and this contradicts $2^m\vert x$. I can split this sum as
$$
x = \sum_{k=m}^n a_k2^k + \sum_{k=0}^{m-1} a_k2^k.
$$
$2^m \vert 2^k$ for $k \geq m$ which means $2^m$ divides the first summation. This means
$$
x \equiv \sum_{k=0}^{m-1} a_k2^k \pmod {2^m}.
$$
But by assumption $2^m \vert x$ which means that in fact
$$
\sum_{k=0}^{m-1} a_k2^k \equiv 0 \pmod {2^m}.
$$
The largest that $\sum_{k=0}^{m-1} a_k2^k$ can be is if every $a_k$ is $1$, which means
$$
0 \leq \sum_{k=0}^{m-1} a_k2^k \leq \sum_{k=0}^{m-1} 2^k = \frac{1 – 2^m}{1-2} = 2^m – 1 < 2^m
$$
so the only way to have
$$
\sum_{k=0}^{m-1} a_k2^k \equiv 0 \pmod {2^m}
$$
is if $a_0 = a_1 = \dots a_{m-1} = 0$
which shows that the final $m$ places of $x$ are $0$.
$\square$
This shows that in binary $8n$ ends in $000$. Adding $1$, $3$, $5$, and $7$ then gets me numbers ending in $001$, $011$, $101$, $111$, and all the remaining digits are the same. This means the XOR of these numbers is only determined by these last 3 places, and
$$
001 \oplus 011 \oplus 101 \oplus 111 = 0
$$
so
$$
\bigoplus_{x=8n}^{x=8n+7} A_x = 0
$$
for any $n\in\mathbb N$.
Letting $y \in \mathbb N$ I have (by Euclidean division) that $y = 8n + a$ for unique $n, a \in \mathbb N$ with $a \leq 7$. This means
$$
F(y) = \bigoplus_{x = 8n}^{8n + a} A_x.
$$
Suppose $a$ is odd. Then there will be an even number of terms in that XOR product so the result will be
$$
F(y) = (8n+1) \oplus \dots \oplus (8n + a)
$$
which is at most $3$ XOR evaluations.
If instead $a$ is even there will be one $A_x$ term left so
$$
F(y) = (8n+1) \oplus \dots \oplus (8n + a – 1) \oplus A_y.
$$
This is also at most $3$ XOR evaluations but it also means I’ll still want a fast way to evaluate $A_x$ by itself.
Let $x \in \mathbb N$ and suppose $4\vert x$. Consider
$$
\bigoplus_{i=0}^3 (x+i).
$$
By Lemma 1 I know $x$ ends in at least two $0$s, so I have four numbers ending in $00$, $01$, $10$, and $11$ respectively, with the remaining digits identical. This means $\bigoplus_{i=0}^3 (x+i) = 0$.
Now for any $x \in \mathbb N$ I have $x = 4m + b$ with $m, b \in \mathbb N$ unique and $b < 4$. The above result shows
$$
A_x = \bigoplus_{k = 4m}^{4m+b} k
$$
which is at most $3$ XORs. But I’ll only end up here if $x$ is even which means $b \in \{0,2\}$ so as far as $F$ is concerned, this term can contribute at most $2$. Also I don’t need to recompute $(m,b)$ if I already have $(n, a)$ since $m = 2n$ and $b$ follows.
This shows that I can evaluate $F(r)\oplus F(\ell – 1)$ in at most $10$ XORs, and that upper bound does not depend on $\ell$ or $r$.