Favourite Operation

Hard
0/120
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Amazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Simulate the Problem Statement.

Approaches (2)
Brute Force

 

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.
Time Complexity

O(N^2) , where ‘N’ is the size of array ‘A’.
 

We are calculating ‘AND’ of all subarrays, so the overall time complexity is O( N^2 ).

Space Complexity

O(1)

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Favourite Operation
Full screen
Console