XOR using Tries - Part 2

Before you go on, please make sure you have read Part 1.

Great! Let’s talk about the next usecase.

Problem

Given an array of integers, find the maximum xor subarray. Or simply,
Given a₁, a₂, ....., a_n, find i and j , i <= j, such that a_i xor a_i+1 xor ..... a_j-1 xor a_j is the maximum possible value.

Simple solution

Run two loops and for every combination of i and j, run one more loop to calculate xor from index i to j.

maxSoFar = -1
For i = 1 to N
For j = i to N
xorVal = 1
For k = i to j
xorVal = xorVal ^ a[k]
maxSoFar = max(maxSoFar, xorVal)
print maxSoFar

That is an O(N^{​​​​​​​3})! Can we simplify it a bit?

Let’s start slow.

Better solution

Let’s first see, where we can optimise it.

Now, running two loops to get each combination of i and j is fine. What about running the loop from index i to index j to calculate xor?

Suppose, you have calculated xor from index 2 to 5, and later on, to calculate from index 2 to 7, why would you calculate xor from index 2 to 5 again?

Or suppose, if you want xor from index 1 to 4, you already know, xor from index 2 to 4 in the process of calculating from index 2 to 5 and just need to xor it with 1, right?

So, we need some means of storing things.

Let’s optimise here first.

What we will be using here is called a precomputed array.

Precomputed array is an array which has computations which we make in the starting and use them later on.

What do we need to precompute here?
Let’s see.

What if I store the xor values of index 1 to index i in array[i] and form the array for i = 1 to N.

What I mean is, suppose we have an array,

2, 4, 3, 6, 8, 7

If I can store an array as

{^ indicates xor}

2, 2^4, 2^4^3, 2^4^3^6, 2^4^3^6^8, 2^4^3^6^8^7

pre[i] = pre[i-1] xor a[i]

This is the precomputation we will do, this array will be the precomputed array. But why are we doing this exactly?

Let’s see the properties of xor once again.

Triangular property of xor is,

[A xor B = C] => [B xor C = A] => [A xor C = B]

So, suppose, I need to find, xor from 3rd element to 5th element,

That is,

3 ^ 6 ^ 8.

Now,

2^4^3^6^8 = (2^4) ^ (3^6^8)

Now, with the triangular property, I can write it as

3^6^8 = (2^4^3^6^8) ^ (2^4)

Which is the xor of 2nd and 5th element in the precomputed array.

So, xor from 3rd to 5th element is the xor of pre[2] and pre[5].

So generally speaking,

A_i xor A_i+1 xor .... A_j = pre[i-1] xor pre[j]

Or in speaking terms, the xor of numbers from index i to j, is the xor of (xor of numbers from 1 to i) and (xor of numbers from 1 to j).

Great, so once we build the precomputed array, we can calculate xor from index i to index j, in constant time.

Given this, we need to run just two loops now, and for each pair of i and j, we need to find the max out of all [(xor 1 to i) xor (xor 1 to j)].

So, this, now takes, O(N²).

Still, not enough, we can optimise it more.

Optimised solution

Let’s use tries like in the previous use case.

Let us rewrite the original problem.

Given a₁, a₂, .... a_n, find i and j , i <= j, such that a_i xor a_i+1 xor .... a_j-1 xor a_j is the maximum possible value.

Can now be written (thanks to precomputed array) as,

Given a₁, a₂, .... a_n, find i and j , i <= j, such that (xor from 1 to i) xor (xor from 1 to j) is maximum.

So, basically, since we have values in precomputed array as 1 to i, we need to find two numbers from the precomputed array, whose xor is maximum.

Hold on, wasn’t that the same question in the previous usecase?

Except that, in the previous usecase, we found out two numbers with maximum xor from given array, and here we are trying to find two numbers with maximum xor from precomputed array, since, our precomputed array consists of numbers from 1 to that index of the original array.

That’s it, you find the precomputed array, consider this as the original array and proceed exactly as in the previous usecase.

This is the optimised solution.

The complexity is :

O(NlogMAX) + O(N) [for creating precomputed array] = O(NlogMAX), same as the previous usecase.

We will explore the next usecase in another problem.