XOR Subarrays :
Difficulty Level : Hard
Submissions : 945
Asked In :
Marks :20
: 16 | : 3
You are given an Array $$$A$$$ containing $$$n$$$ integers and an integer $$$x$$$.
Find the minimum value $$$k$$$ such that the number of subarrays of $$$A$$$ having $$$XOR$$$ value of at most $$$k$$$ is atleast $$$x$$$.
An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself. The $$$XOR$$$ value of a subarray is the $$$XOR$$$ of values of elements in the subarray.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of testcases.
The first line of each testcase contains two space separated integers $$$n$$$ $$$(1 \le n \le 5 \cdot 10^{4})$$$ and $$$x$$$ $$$(1 \le x \le n*(n+1)/2)$$$ — the number of elements in the array $$$A$$$ and the value of $$$x$$$ as described in the problem statement.
The second line consists of $$$n$$$ space separated integers - $$$A_1, A_2......., A_n$$$ $$$(1 \le A_i \le 10^6)$$$ — the elements of the array $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$5 \cdot 10^4$$$.
For each test case, print the minimum value of $$$k$$$ satisfying the constraints in a single new line.
14 71 2 3 4
4
In sample test case,
Given number of subarrays to be atleast $$$7$$$, i.e. $$$x = 7.$$$
So if we select the value for $$$k$$$ to be $$$3$$$, number of subarrays of $$$A$$$ having $$$XOR$$$ value atmost $$$3$$$ is $$$6$$$.
If we select the minimum value for $$$k$$$ to be $$$4$$$, number of subarrays of $$$A$$$ having $$$XOR$$$ value atmost $$$4$$$ is $$$8$$$.
So, the minimum value of $$$k$$$ for which number of subarrays of $$$A$$$ is atleast $$$7$$$, each of which have $$$XOR$$$ value of atmost $$$k$$$ is $$$4$$$.
