The Subarray XOR solution codechef – Given an array AA having NN elements, a subarray SS of AA is called good if XOR(S)≥KXOR(S)≥K, where XOR(S)XOR(S) denotes the bitwise XOR of all the elements of the subarray SS.
Table of Contents
[Solution] The Subarray XOR solution codechef
Find the length of the smallest subarray SS which is good. If there is no good subarray, print −1−1 instead.
Input Format
- The first line of input contains a single integer TT, denoting the number of test cases. The description of the TT test cases follows.
- The first line of each test case contains two space-separated integers NN and KK – as described in the problem statement.
- The second line of each test case contains NN space-separated integers A1,A2,...,ANA1,A2,…,AN, AiAi representing the elements of the array AA.
Output Format
For each test case, output in a single line, the length of the shortest subarray which is good. If there is no good subarray, print −1−1.
The Subarray XOR solution codechef
- 1≤T≤2⋅1041≤T≤2⋅104
- 1≤N≤1051≤N≤105
- 0≤Ai<2300≤Ai<230
- 0≤K<2310≤K<231
- Sum of NN over all test cases does not exceed 2⋅1052⋅105.
Sample Input 1
3
5 15
1 4 2 8 1
5 7
1 4 2 8 1
5 20
1 4 2 8 1
Sample Output 1
4
1
-1
The Subarray XOR solution codechef Explanation
Test case 11: For S=[A1,A2,A3,A4]S=[A1,A2,A3,A4], XOR(S)=1⊕4⊕2⊕8=15XOR(S)=1⊕4⊕2⊕8=15. Similarly, for S=[A2,A3,A4,A5]S=[A2,A3,A4,A5], XOR(S)=4⊕2⊕8⊕1=15XOR(S)=4⊕2⊕8⊕1=15. These are the only two subarrays which are good. The length of these subarrays is 44. It can be proven that no subarray of length less than 44 is good.
Test case 22: There are several good subarrays. Some examples are S=[A4]S=[A4], S=[A1,A2,A3]S=[A1,A2,A3], and S=[A3,A4]S=[A3,A4]. The length of the smallest subarray is 11, and that subarray is [A4][A4]. It can be proven that no subarray of length less than 11 is good.
Test case 33: There is no subarray SS such that XOR(S)≥20XOR(S)≥20. Hence, there is no good subarray.