# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Lavish Gupta

Tester: Abhinav Sharma, Nishank Suresh

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2521

# PREREQUISITES:

None

# PROBLEM:

Given an array A having N elements, a subarray S of A is called `good`

if XOR(S) \geq K, where XOR(S) denotes the bitwise XOR of all the elements of the subarray S.

Find the length of the **smallest** subarray S which is `good`

. If there is no `good`

subarray, print -1 instead.

# EXPLANATION:

**XOR Property**: If A \oplus B = K, then

Let us first solve a subproblem of this where we need to calculate the length of the smallest subarray S such that XOR(S) = K.

For this we first calculate prefix\_xor, where

Taking initial value of ans as n+1 and a map m

we loop through the array and for a position say i we check as follows:

Along with this at each step we also update m as: m[prefix\_xor[i]] = i

Thus at the end of our iterations, if ans = (n+1), then no such subarray exists otherwise the length of the smallest subarray is ans.

Now coming back to the original problem, we can initially get the smallest length of subarray S where XOR(S) = K. Now representing K as:

where K_i represents the i_{th} bit of K.

Looping through the bits of K, we check for the i_{th}, bit, if K_i is 0, then we can take K' as follows:

Thus to get K', we set the i_{th} bit of K as 1 and unset all bits of K, post that. Similarly let us define A' as

Thus to get A'[j], we set all the bits, post the i_{th} of A[j] to 0

Now with A' and K', we can again check for smallest subarray S', such that XOR(S') = K'.

By the end of our loop we will get the length of the smallest subarray S, such that XOR(S) \geq K if it exists.

To understand why this work we can see that when we loop from left to right on bits of K, and encounter an unset bit, we change the unset bit of K to set bit, which essentially increases the value of K. The other part is that we unset all the bits post the i_{th} bit , so through this we are actually ignoring these bits and only comparing the bits before and including the i_{th} in our algorithm because if these bits are equal then no matter what the bits are after, the XOR of the subarray would be greater than K.

# TIME COMPLEXITY:

O(NlogN), for each test case.

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester1’s Solution

Tester2’s Solution