0

Favourite Operation

Difficulty: HARD
Contributed By
Ashish Kumar
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

You are given an array ‘A’ having ‘N’ integers and an integer ‘K’. You first calculate the bitwise ‘AND’ of all subarrays having size at most ‘K’. Then you take the bitwise ‘XOR’ of all these ‘AND’ results.

Your task is to output the integer you receive after performing the above operations.

Example :
N = 3
K = 2
A = [ 1, 2, 3 ]

Explanation : 

The bitwise ‘AND’ of all subarrays of size <= 2 are : 

From index 1 : 
Subarray of length 1 has ‘AND’ = 1.
Subarray of length 2 has ‘AND’ = 1 & 2 = 0.

From index 2 : 
Subarray of length 1 has ‘AND’ = 2.
Subarray of length 2 has ‘AND’ = 2 & 3 = 2.

From index 3 : 
Subarray of length 1 has ‘AND’ = 3.

‘XOR’ of all these ‘AND’ operations = 1 ^ 0 ^ 2 ^ 2 ^ 3 = 2.

So, final result = 2.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘K’.

The second line of each test case contains an array ‘A’ of size ‘N’.
Output format :
For each test case, print one integer denoting the final result after performing the operations.

Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 10^5
1 <= K <= N
1 <= A[i] <= 10^5    

Time Limit : 1 sec
Sample Input 1 :
2
4 2
1 2 3 4
3 3
4 8 2
Sample Output 1 :
6
14
Explanation Of Sample Input 1 :
For test case 1 we have, 

The bitwise ‘AND’ of all subarrays of size <= 2 is : 1, 2, 3, 4, 0, 2, 0.

 The bitwise ‘XOR’ of all ‘AND’ operations is : 6

So, we output 6.

For test case 2 we have,

The bitwise ‘AND’ of all subarrays of size <= 3 is : 4, 8, 2, 0, 0, 0.

The bitwise ‘XOR’ of all ‘AND’ operations is : 14

So, we output 14.
Sample Input 2 :
3
3 2
6 5 2 
2 1
9 7 
3 1
5 2 4 
Sample Output 2 :
5
14
3
Reset Code
Full screen
copy-code
Console