length of subarray with xor = 0

i want to get the length of all the subarrays having xor = 0. For example if arr is 2,5,7,1,3 then subarrays with xor = 0 are 2,5,7 and 5,7,1,3. i have this code which return 2 as no of subarrays with xor = 0 but i also want to know their length. And time limit is 1s so can't use nested loop as constraint of size of array is upto 10^5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h> 
using namespace std; 
  
// Returns count of subarrays of arr with XOR 
// value equals to m 
long long subarrayXor(int arr[], int n, int m) 
{ 
    long long ans = 0; // Initialize answer to be returned 
  
    // Create a prefix xor-sum array such that 
    // xorArr[i] has value equal to XOR 
    // of all elements in arr[0 ..... i] 
    int* xorArr = new int[n]; 
  
    // Create map that stores number of prefix array 
    // elements corresponding to a XOR value 
    unordered_map<int, int> mp; 
  
    // Initialize first element of prefix array 
    xorArr[0] = arr[0]; 
  
    // Computing the prefix array. 
    for (int i = 1; i < n; i++) 
        xorArr[i] = xorArr[i - 1] ^ arr[i]; 
  
    // Calculate the answer 
    for (int i = 0; i < n; i++) { 
        // Find XOR of current prefix with m. 
        int tmp = m ^ xorArr[i]; 
  
        // If above XOR exists in map, then there 
        // is another previous prefix with same 
        // XOR, i.e., there is a subarray ending 
        // at i with XOR equal to m. 
        ans = ans + ((long long)mp[tmp]); 
  
        // If this subarray has XOR equal to m itself. 
        if (xorArr[i] == m) 
            ans++; 
  
        // Add the XOR of this subarray to the map 
        mp[xorArr[i]]++; 
    } 
  
    // Return total count of subarrays having XOR of 
    // elements as given value m 
    return ans; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int arr[] = { 2,5,7,1,3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int m = 0; 
  
    cout << "Number of subarrays having given XOR is "
         << subarrayXor(arr, n, m); 
    return 0; 
} 
You should post the URL to your quiz site as well.
Just so we can see the actual problem to be solved.

Plus, you didn't ask a question.
my question is how do i find the length of the subarrays whose xor is 0. for example in 2 5 7 1 3, 2 5 7 has xor 0 so i need length as 3 and 5 7 1 3 has xor 0 so i need length as 4 but my code only returns no of such subarrays i.e. 2
> // Return total count of subarrays having XOR of
> // elements as given value m
> return ans;

You only get 2, because that's all you return.

If you want the rest of the information like
- length 3 starting at index 0
- length 4 starting at index 1
Then just return mp or whatever - it's your code.

Plus, you leak memory by never freeing xorArr.


Edit:

Whatever, you're just another chancer trying to cheat on some programming contest.

Original code here:
https://www.geeksforgeeks.org/count-number-subarrays-given-xor/

1
2
3
4
5
6
7
8
9
10
11
12
13
$ diff -b 1st_file.txt 2nd_file.txt 
0a1,3
> // C++ Program to count all subarrays having 
> // XOR of elements as given value m with 
> // O(n) time complexity. 
53c56
<     int arr[] = { 2,5,7,1,3 }; 
--
> 	int arr[] = { 4, 2, 2, 6, 4 }; 
55c58
<     int m = 0; 
--
> 	int m = 6; 

All you did was rip off the initial comment and change the array of numbers.

If you'd actually WRITTEN that code yourself, you wouldn't be asking such a basic question like "but I also need the length". If you knew how the code actually worked (because you'd written it), then you would already know that.

Last edited on
Registered users can post here. Sign in or register to post.