Last Updated: 7 Oct, 2021
Favourite Operation
Hard
Asked in company
Ninja has recently studied operators ‘AND’ and ‘XOR’. His teacher gave him an assignment related to the two operators but Ninja is taking a lot of time to compute it and he is afraid he would be unable to complete the assignment before the deadline. Ninja has asked you to help him complete the assignment before the deadline.
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
Approaches
Approach :
- We perform the steps as told in the problem statement.
- Find all subarrays not greater than the size of ‘K’.
- Take the bitwise ‘AND’ of all these subarrays.
- Take ‘XOR’ of all the bitwise ‘AND’ results obtained.
- This is the required result.
Algorithm :
- Initialize a variable ‘ans’ as ‘0’.
- Run a for loop from ‘i = 0’ to ‘i = N-1’ :
- Initialize a variable ‘allAnd’ as ‘A[i]’.
- Run a for loop from ‘j=i’ to ‘j = N-1’.
- If ‘j - i >= k’, break out of the loop.
- Perform the ‘AND’ of ‘allAnd’ with ‘A[j]’.
- Perform the ‘XOR’ of ‘ans’ with ‘allAnd’.
- Return the ‘ans’ as final result.
Approach :
- We first represent each element of the array ‘A’ by bits.
- Next, we notice that in calculating ‘AND’ of any subarray, a particular bit will be set only if all the bits in the subarray are set.
- So, we represent the array ‘A’ in bits.
- Next, for any bit of the answer, we check the total non-intersecting subarrays having this particular bit set.
- Let us say the size of any of these subarrays is ‘X’.
- Then two cases arise :
- If ‘X’ <= ‘K’ :
- Then all subarrays will be valid so total ‘(X*(X+1))/2’ subarrays will be added which are having the current bit set.
- If ‘X’ > ‘K’ :
- Total subarrays of size <= ‘K’ are :
- (X-K+1)*(K)*(K+1)/2 - (X-K)(K-1)(K)/2
- There will be total ‘X-K+1’ subarrays of size ‘K’ and ‘X-K’ subarrays of size ‘K-1’ which are calculated twice in the above subarrays.
- After calculating the total ‘AND’ subarrays having a particular bit set, we check if this is odd/even.
- If even, then the ‘XOR’ bit will be unset, else it will be set.
- Let us understand the approach by an example :
- Let A = [ 3, 7, 5, 7 ] and K = 1.
- We first represent the array ‘A’ in bits :
- A = [ 011, 111 , 101, 111 ]
- Let us check if the 2nd bit from LSB will be present in our answer or not.
- The non-intersecting subarrays with all 2nd bits set are :
- [ 011, 111 ] and [ 111 ].
- So, the first has a size of 2 which is greater than ‘K’.
- So, its contribution is : ( 2-1+1)*(1)*(1+1)/2 - ( 2-1)*(0)*(1)/2 = 2.
- The next one has a size of 1, which is <= ‘K’.
- So, its contribution is 1*(1+1)/2 = 1.
- The total contribution of the current bit is 2+1 = 3.
- Since this value is odd, the current bit will be set in the final answer.
- Similarly, we calculate the contribution of each bit and whether it will be set in the answer.
Algorithm :
- Initialize a variable ‘ans’ as ‘0’.
- Initialize a 2-D array ‘bits’ with row size ‘N’ and column size ‘20’.
- Store the bits of the array ‘A’ in the array ‘bits’.
- Traverse over the bits from ‘i=0’ to ‘i=19’ :
- Initialise ‘j’ = 0 and ‘X’ = 0 and ‘cnt’ = 0.
- Run a while loop till ‘j’<N :
- If the current bit ‘i’ of ‘A[j]’ is set, increment ‘X’.
- Else, calculate the contribution on the basis of :
- If ‘X’ > ‘K’ , increment ‘cnt’ by : (X-K+1)*(K)*(K+1)/2 - (X-K)(K-1)(K)/2.
- Else, increment ‘cnt’ by : (X*(X+1))/2
- Update ‘X’ = 0.
- Increment ‘j’.
- If ‘cnt’ is odd, increment ‘ans’ by 2^i as the current bit will be set.
- Return the ‘ans’ as the final result.