In this tutorial, we’ll present the problem of finding the XOR of all numbers in a given range.
First, we’ll explain the naive approach. Then, we’ll see how we can improve it in order to obtain a better solution. Finally, we’ll present a comparison between both approaches.
2. Defining the Problem
In this problem, we’re given an array of size and multiple queries. In each query, we’re asked to calculate the bitwise XOR operation between all the elements in range .
The array doesn’t change between queries. In other words, there are no queries that ask us to change the value of a certain element inside the array.
Therefore, for each query inside the array , we must return the value of , where is the bitwise XOR operation between the elements in the range .
3. XOR Background
As we know, the bitwise XOR operation works on the two numbers bit by bit. For each bit, the result can be extracted from the presented table:
As we can see, if both bits are similar, then the XOR equals to zero. Otherwise, the result equals to one. Put differently, the bitwise XOR operation equals zero in case the number of ones is even and equals one in case the number of ones is odd.
Also, an important thing to notice is that the bitwise XOR works on each bit independently. In other words, the result of each bit doesn’t affect the result of any other bits inside the number. Keep these notes in mind when we discuss the solution in section 5.
4. Naive Approach
First, we’ll explore the naive approach. Let’s take a look at its algorithm:
In the beginning, the algorithm sets the answer to zero. After that, we iterate over the elements of the range and calculate the XOR of all of its elements. Finally, we return the calculated answer.
The complexity of the naive approach is , where is the size of the array. The reason behind this complexity is that we might end up iterating over all the elements in the worst case.
Therefore, the complexity of each query is linear.
5. Prefix-XOR Approach
Let’s try to improve our naive approach.
5.1. Precalculation Idea
Since each bit is calculated separately, we can solve the problem for each bit independently. After that, we can create a complete solution.
Suppose the problem was to handle individual bits. Same as before, we need to calculate the XOR for this bit in the range . First, let’s create a boolean array named . In each cell , we’ll store the prefix XOR of all bits in the range .
From the definition of the XOR operation in section 3, we can see that if the number of bits in the ith prefix is even, then the ith cell will equal to zero. Otherwise, the ith cell will equal to one.
Now, let’s check the original problem. We need to find the XOR of bits in the range — in other words, whether the number of ones in the range is even or odd.
To do this, let’s consider two values. The first value is , which covers the range . This range covers all the elements from the needed range, plus some extra elements which are in the range . Therefore, the second value is , which covers the range .
From these two values, we can conclude the value of the range .
5.2. Solution Idea
After calculating the array, we have four cases to consider in each query:
- Both and equal zero. Since equals zero, the number of ones is even before starting the range . Also, the number of ones remains even after processing the range . This can only happen if the number of ones in the range is even as well.
- Both and equal one. Since equals ones, the number of ones is odd before entering the range . Also, since equals one, the number of ones in this range is also odd. This can only hold if the number of ones in the range is even, which causes the parity of the bit to remain the same.
- equals one, while equals zero. Since the number of ones in the range is odd, but then changes to be even in the range , we can conclude that the number of ones in the range is odd.
- equals zero, while equals one. Since the number of ones in the range is even, but then changes to be odd in the range , we can conclude that the number of ones in the range is odd.
We can see that if both and have the same value, then the answer is zero. Otherwise, the answer equals one.
This is equivalent to performing the XOR operation between and . Therefore, the answer is simply , where is the bitwise XOR operation.
5.3. Precalculation Algorithm
In order to form a general solution, we need to calculate the prefix XOR array .
Let’s take a look at the implementation of this step:
The idea is based on dynamic programming. In the beginning, we know that the answer of equals zero.
Next, for each range , we can calculate its answer from the range . The only difference between these two ranges is . Therefore, we need to add to the range . In other words, . In the end, we return the calculated array .
The complexity of the precalculation step is , where is the number of elements in the array .
5.4. Answering the Queries
After building the array, we can answer each query with the same approach discussed in section 5.2.
Let’s take a look at the algorithm of answering the queries:
As we can see, we just return the XOR between and as discussed in section 5.2. The complexity of answering each query is .
Consider the table that shows a comparison between both approaches:
Obviously, the prefix XOR approach is better when it comes to comparing complexities. However, it requires us to calculate the array in advance. After that, we can answer each query efficiently at the complexity of .
One thing to keep in mind is that this only holds when we don’t change the values of the elements in the array . When we have two types of queries, either changing the value of a single element or answering a query of the XOR of elements in the range , both approaches have the same complexity.
Therefore, we can use the naive approach, which is simpler.
In this tutorial, we explained the problem of calculating the XOR of a given range of numbers. First, we presented the naive approach. Next, we discussed the theoretical idea and implementation of the prefix XOR approach.
Finally, we presented a summary comparison between the two approaches.