Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 3 Feb, 2021

Moderate

```
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’.
```

```
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.
```

```
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.
```

```
You don’t need to print anything; It has already been taken care of.
```

```
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
```

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**.

- 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]. - 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**.

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

- Increment

- Iterate

- We will maintain a variable
- Return the variable
**ans**.

The basic idea of this approach is to use a HashMap to store the prefix XOR of the subarray. We’ll iterate over the given array/list and calculate the number of subarrays ending at a particular index and having an XOR sum of ‘X’.

Now consider the following steps:

- Create a HashMap “prefXor” which stores the count of subarrays having a particular XOR value.
- Create a variable “curXor” which stores the XOR for ‘i’ elements. Initialise it with zero. Also, create a variable called “ans” to store the count of the subarrays having XOR ‘X’.
- Start iterating through given array/list using a variable ‘i’ such that 0 <= ‘i’ < n
- Update the “curXor” i.e.
**curXor = curXor ^ arr[i]** - Store the required value of the prefix Xor to make the XOR of the subarray ending at the current index equal to X i.e.
**req = X ^ curXor** - Now add the count of prefix arrays with required xor i.e.
**ans = ans + prefXor[req]** - Update the “prefXor” HashMap with the “curXor” i.e.
**prefXor[curXor] = prefXor[curXor] + 1**

- Update the “curXor” i.e.

Similar problems

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Maximum GCD

Hard

Posted: 8 Dec, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023