Count of Subarrays in the Range [L, R] having XOR + 1 equal to XOR (XOR) 1 for M Queries

Approach 1: Brute Force

The most straightforward approach will be to scan through all the subarrays, calculate the XOR for each subarray, and check if XOR + 1 = XOR ^ 1. We'll do this for each query and increment a 'COUNT' variable. To iterate through each subarray in the range 'L' to 'R,' we'll write nested loops where the outer Loop will iterate from 'L' to 'R,' and the inner Loop will iterate from 'i' to 'R.' Let's see how the algorithm works.

We'll have to function here countRangeLR(), which returns the Count of subarrays that satisfy the above condition, and countSubarrayRange(), which replaces the count vector for each query. Let's try to analyze the functions.

countRangeLR()

Parameters

1. 'ARR' - Input array.
2. 'L' - Start of the range of the array.
3. 'R' - End of the range of the array.

Working

1. Firstly, we initialize the variable 'COUNT' to store the Count of subarrays in the range [L, R] whose XOR + 1 = XOR ^ 1.
2. Next, we loop through the range [L, R], and at each index 'i' we initialize the 'XOR_SUBARRAY = 0'.
3. Inside this loop we loop from the current index to 'R' and caculate the 'XOR_SUBARRAY', next we check if 'XOR_SUBARRAY + 1 = XOR_SUBARRAY ^ 1', then increment 'COUNT'.
4. At last, return the 'COUNT.'

countSubarrayRange()

Parameters

1. ‘ARR’ - Input array.
2. ‘QUERIES’ - Queries of range [L, R]

Working

1. We initialize a vector 'ANSWER' to store the Count of subarrays for each range [L, R] in the vector 'QUERIES.'
2. Next, we loop through the vector 'QUERIES', call the function countRangeLR() for each range, and push it into the 'ANSWER.'
3. Return 'ANSWER'.

C++ implementation

#include <iostream>
#include <vector>

using namespace std;

// Function to count the number of subarrays whose XOR + 1 = XOR (XOR) 1.
int countRangeLR(vector<int> &arr, int l, int r)
{
   // Initialize the count.
   int count = 0;

   // Loop through range [L, R] and calculate the XOR.
   for (int i = l; i <= r; i++)
   {
       // Initialize XOR for subarray.
       int xorSubarray = 0;
       for (int j = i; j <= r; j++)
       {
           xorSubarray ^= arr[j - 1];

           // Check Condition, increase 'COUNT'.
           if ((xorSubarray + 1) == (xorSubarray ^ 1))
           {
               count++;
           }
       }
   }

   // Return 'COUNT'.
   return count;
}

// Wrapper function.
vector<int> countSubarrayRange(vector<int> &arr, vector<pair<int, int> > queries)
{
   // Number of queries.
   int m = queries.size();

   // Declare answer vector.
   vector<int> answer;

   // Loop through all the queries range.
   for (int i = 0; i < m; i++)
   {
       answer.emplace_back(countRangeLR(arr, queries[i].first, queries[i].second));
   }

   // Return the 'ANSWER'.
   return answer;
}

int main()
{
   int n;
   cout << "Enter the value of N:";
   cin >> n;
   vector<int> arr(n);

   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }

   int m;
   cout << "Enter the value of M:";
   cin >> m;

   cout << "Enter the queries [L, R]:\n";
   vector<pair<int, int> > queries(m);

   for (int i = 0; i < m; i++)
   {
       cin >> queries[i].first >> queries[i].second;
   }

   vector<int> countArray = countSubarrayRange(arr, queries);

   cout << "The count of subarrays in the range [L, R] which satisfy the given condition is: ";
   for (int &x : countArray)
   {
       cout << x << "  ";
   }
   cout << endl;

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Output

Time Complexity

O(M * (N ^ 2)), where 'N' = size of the array 'ARR' and 'M' = size of the array. 'QUERIES. '

Looping through each subarray and calculating XOR takes O(N^2) time, and there are 'M' queries. Hence the total time for all queries = O(M * (N ^ 2)).

Space Complexity

O(1)

As we are not using any extra auxiliary space.

Approach 2 - Parity 

One of the essential points in the problem is that when an even number is XORed with one, the result is Number plus one, and when an odd number is XORed with one, the result is Number minus one.

We can use this observation to solve the question. So every subarray whose XOR is even or the Number of odd elements in that subarray is even will contribute to the Count. Now the question is, we still need to calculate the XOR for each subarray. This will result in time complexity O(M * (N ^ 2)). And hence we will calculate the Number of odd numbers until each index which will be stored in an array 'EVEN_SUBARRAY'. We'll do this by using an extra array 'PARITY' where 'PARITY[i] = ARR[i] + PARITY[i-1]' (to find whether the subarray from [0 - i] is even or odd).

Let's see how the algorithm works.

evenSubarrayRange()

Parameters

• ‘ARR’ - Input Array.
• ‘QUERIES’ - Queries of range [L, R]

Working

• We insert a dummy element at the start of the ARR array.
• Next, we initialize two vectors, 'PARITY' and 'EVEN_SUBARRAY.'
• Now count the even-count odd numbers subarray by iterating across the array.
• Then, Initialize a vector 'ANSWER.'
• Next, we loop through each 'M' query and calculate the Number of even and odd sum subarray. Then we calculate and push the Count to 'ANSWER.'
• Return 'ANSWER'.

C++ implementation

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
// Function to evenSubarray all subarrays in ranges [L, R].
vector<int> evenSubarrayRange(vector<int> &arr, vector<pair<int, int>> queries)
{
   arr.insert(arr.begin(), 0);
   // Number of queries.
   int m = queries.size();
   int n = arr.size();
   vector<int> parity(n + 1, 0), evenSubarray(n + 1, 0);
   for (int i = 1; i < n; i++)
   {
       parity[i] = (parity[i - 1] + arr[i]) % 2;
       evenSubarray[i] = evenSubarray[i - 1];
       if (parity[i] % 2 == 0)
           evenSubarray[i]++;
   }
   // Initialize answer.
   vector<int> answer;
   // Loop through all the queries range.
   for (int i = 0; i < m; i++)
   {
       int l = queries[i].first;
       int r = queries[i].second;
       int even = evenSubarray[r] - evenSubarray[l - 1];
       int odd = (r - l + 1) - even;
       if (parity[l - 1] == 1)
       {
           swap(even, odd);
       }
       even++;
       int subevenSubarray = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;
       answer.emplace_back(subevenSubarray);
   }
   // Return the 'ANSWER'.
   return answer;
}
int main()
{
   int n;
   cout << "Enter the value of N:";
   cin >> n;
   vector<int> arr(n);
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   int m;
   cout << "Enter the value of M:";
   cin >> m;
   vector<pair<int, int>> queries(m);
   for (int i = 0; i < m; i++)
   {
       cin >> queries[i].first >> queries[i].second;
   }
   vector<int> evenSubarrayArray = evenSubarrayRange(arr, queries);
   cout << "evenSubarray of Subarrays in ranges which satisfy the given condition are: ";
   for (auto x : evenSubarrayArray)
   {
       cout << x << "  ";
   }
   cout << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Output

Time Complexity

O(N + M), where ‘N’ = size of the array ‘ARR’ and ‘M’ = size of the array.

As we are traversing both arrays ones. Hence the time complexity = O(N + M).

Space Complexity

O(N), where ‘N’ = Size of ‘ARR’.

Since we are creating two arrays ‘PARITY’ and ‘EVEN_SUBARRAY’ of the size of ‘N’. Hence the space complexity is O(N).

Check out this problem - Subarray With 0 Sum

Frequently Asked Questions

What is an array in C++?

An array is a data structure in C++ that allows you to store multiple values of the same type.

What is the purpose of an array?

Arrays are best for storing several values in a single variable and processing a large number of matters quickly. Using the indices, we can promptly retrieve the array elements. In any programming language, arrays are the most commonly used data type.

In C, what is array decay?

Array decay is the loss of an array's type and dimensions. It happens when we use a pointer or a value to send a variety into a function. The array receives the initial address, which is a pointer. As a result, the array's size differs from the original.

In C++, how do you pass an array by reference?

A whole array cannot be passed as an argument to a function in C++. You can, however, supply a pointer to an array without an index by specifying the array's name.

In C, what is the difference between a pointer and an array?

In C, an array is used to store elements of the same type, whereas a pointer is an address variable that holds a variable's address. A pointer can point to the array variable's address, and the array can be traversed using a pointer.

Conclusion

Finally, you have reached the article's conclusion. Congratulations!! You gained knowledge of the Count of subarrays in the range [L, R] having XOR + 1 equal to XOR (XOR) 1 for M queries in this blog.

Are you eager to read more articles on array questions for Interview? Coding Ninjas cover you, so don't worry. View more topics on Coding ninjas.

Recommended problems -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k

Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!