Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 1: Brute Force
3.1.
countRangeLR()
3.1.1.
Parameters
3.1.2.
Working
3.2.
countSubarrayRange()
3.2.1.
Parameters
3.2.2.
Working
3.3.
C++ implementation
3.4.
Input
3.5.
Output
3.6.
Time Complexity
3.7.
Space Complexity
4.
Approach 2 - Parity 
4.1.
evenSubarrayRange()
4.1.1.
Parameters
4.1.2.
Working
4.2.
C++ implementation
4.3.
Input
4.4.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is an array in C++?
5.2.
What is the purpose of an array?
5.3.
In C, what is array decay?
5.4.
In C++, how do you pass an array by reference?
5.5.
In C, what is the difference between a pointer and an array?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Pair Programming is an exciting concept in our tech world, in which two programmers work on the same machine where one writes code(Driver) and the other Directs(Navigator). So Let's solve this problem by pair programmers style. I'll be the navigator & you be the Driver.

Today we'll be solving an exciting array problem. So let's get started.

Problem Statement

problem statement

You are given an array of integers 'ARR' of size 'N' and 'M' number of queries [Li, Ri]. Find the Count of all the subarrays between range [L, R] that satisfy the following condition.

Note - Both L and R denote 0-based indexing in the array.

Condition

If XOR of all the elements in subarray = 'XOR_SUBARRAY', then

'XOR_SUBARRAY + 1 = XOR_SUBARRAY XOR 1'.

Example

Example

Must see about, kth largest element in an array and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1: Brute Force

xor truth table

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;
}

Input

input for the program

Output

output for the program

Time Complexity

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

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.

Algorithm Apporach 2

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;
}

Input

input for the program

Output

output for the program

Time Complexity

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

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 -

 

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!

Previous article
Find an array element such that all elements are divisible by it
Next article
Count Different Substrings in a String
Live masterclass