Count Subarrays with Given XOR

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
126 upvotes
Asked in companies
SamsungHCL TechnologiesArcesium

Problem statement

Given an array of integers ‘ARR’ and an integer ‘X’, you are supposed to find the number of subarrays of 'ARR' which have bitwise XOR of the elements equal to 'X'.

Note: 
An array ‘B’ is a subarray of an array ‘A’ if ‘B’ that can be obtained by deletion of, several elements(possibly none) from the start of ‘A’ and several elements(possibly none) from the end of ‘A’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains two integers ‘N’ and ‘X’ separated by a single space, denoting the number of elements in the array and the required subarray XOR respectively.

The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array.
Output Format : 
For each test case, print on a new line the number of subarrays of the given array that have bitwise XOR of the elements equal to ‘X’.

Print the output of each test case in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 10
3 <= N <= 5 * 10 ^ 4
0 <= X <= 10 ^ 9
0 <= ARR[i] <= 10 ^ 9

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of elements in the array, ‘X’ denotes the required subarray XOR and ARR[i] denotes the 'i-th' element of the given array.

Time Limit: 1 sec
Sample Input 1 :
2
5 8
5 3 8 3 10
3 7
5 2 9
Sample Output 1 :
2
1
Explanation of Sample Input 1 :
In the first test case, the subarray from index 1 to index 3 i.e. {3,8,3} and the subarray from index 2 to index 2 i.e. {8} have bitwise XOR equal to 8.

In the second test case, the subarray from index 0 to index 1 i.e. {5,2} has bitwise XOR equal to 7.
Sample Input 2 :
2
6 11
10 1 0 3 4 7
5 4
4 3 1 2 4
Sample Output 2 :
3
4
Hint

Try to solve the problem by travering through each subarray.

Approaches (2)
Brute Force

A simple method is to traverse through each subarray to find the total number of subarrays with the XOR of all elements present in the subarray equal to X.

 

To obtain the total number of rounds after each operation, we will maintain a variable ans, which stores the total number of subarrays. We will iterate the variable index from 0 to N - 1 and in each iteration, we will iterate pos from index to N - 1. 
 

  1. We will maintain a variable currentXor, which will store the XOR of the current subarray. We can directly add arr[pos] to our subarray, as we want only XOR. So we will XOR currentXor with arr[pos].
  2. Now, we will check if currentXor is equal to X, then we will increment the variable ans by 1.

 

In the end, we will return the variable ans.

 

Algorithm:

 

  • Create a variable ans, which stores the total number of subarrays. We will set the variable ans as 0.
  • Iterate index from 0 to N - 1.
    • We will maintain a variable currentXor, which will store the XOR of all elements present in the current subarray. We will set currentXor as 0.
      • Iterate pos from index to M - 1.
        • We can directly add arr[pos] to our subarray, as we want only XOR. So we will XOR currentXor with arr[pos].
        • Check if currentXor is equal to X.
          • Increment ans by 1.
  • Return the variable ans.
Time Complexity

 O(N ^ 2), Where 'N' denotes the number of elements in the given array.

 

We are doing N iteration, and in each iteration, it takes O( N ) time to find XOR of the current subarray. Hence, the overall Time Complexity is O(N ^ 2).

Space Complexity

O(1). 

 

Constant Space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Count Subarrays with Given XOR
Full screen
Console