[1] Representing integers by binary trie

We will represent all integers less than \(2^N\) as the leaves in a binary trie by looking at their digits in the order from lowest to highest. That is, we represent the integers as the leaves of a complete binary tree by classifying them according to

• the \(1\)’s place, the \(2^1\)’s place, the \(2^2\)’s place, \(\ldots\)

in this order.

An intermediate node corresponds to a set of integers equal to some value modulo \(2, 4, \ldots\)

---

[2] Binary trie and Operation \(+\)

Performing Operation \(+\) changes the binary representation of an integer \(x\) changes as follows.

• The \(1\)’s place always changes.
• The \(2^1\)’s place changes if \(x\equiv 1\pmod{2}\).
• The \(2^2\)’s place changes if \(x\equiv 3\pmod{4}\).
• The \(2^3\)’s place changes if \(x\equiv 7\pmod{8}\).
• \(\vdots\)

It corresponds to starting at the root and going in the direction of \(1\), while swapping the two children in the directions of \(0\) and \(1\) at each intermediate node in the path.

---

[3] Binary trie and Operation \(\oplus\)

Performing Operation \(+\) changes, for some places, the binary representation of every integer. It corresponds to swapping the two children in the directions of \(0\) and \(1\) at the intermediate nodes at some depths.

---

[4] The solution to the problem

After all, we can perform the following two kinds of operations on the binary trie:

• Operation (A): Swap the two children of the intermediate nodes at some depths.
• Operation (B): Choose a leaf and swap the two children of the intermediate nodes on the path from the root to the leaf.

The latter operation is enabled by making the chosen leaf reachable via \(1\)’s by Operation \(\oplus\) and then performing Operation \(+\).

Furthermore, we can assume that we never perform Operation (A) on the deepest intermediate nodes (it would be equivalent to performing Operation (B) on every deepest intermediate node). This assumption determines the paths for which we should perform Operation (B). After performing Operation (B) for all such paths, it remains to consider whether we can reach the desired state by performing Operation (A) once, which is easy.

By summarizing the above, the problem can be solved in, for example:

• \(O(N2^N)\) time,
• at most \(2^N\) operations.

One can also solve it in at most \(2^{N-1}\) operations by also performing Operation (A) on the deepest intermediate nodes when appropriate.