In C++, maximize the number of subarrays with zero XOR

We get an array Arr[] containing integer values. The goal is to find the maximum number of subarrays whose XOR is 0. The bits of any subarray can be swapped any number of times.

Note:- 118

In order to make the XOR of any subarray to 0 by swapping bits, two conditions must be met:-

• If the number of setting digits in the range from left to right is an even number.

• For the sum of bits in any given range

Let’s look at various input and output scenarios-

In −Arr[] = { 1,2,5,4 }

Out −

Only the subarray that meets the first condition: 4

Subarray that satisfies two conditions: 3

In − Arr[] = { 3,7,2,9 }

Out −

Subarray condition that only satisfies the first condition: 6

Subarray that satisfies both conditions: 3

In the following program The method used is as follows -

In this method we observe that in order to make the XOR of any sub-array to 0 by swapping bits, two conditions must be fulfilled:- If the range is set from left to right The number of digits is an even number or the sum of digits for any given range

• Get the input array Arr[] and calculate its length.

• Function removeSubarr(int arr[], int len) returns the number of subarrays that do not meet condition 2.

• Set the initial count to 0.

• Iterate over the array using a for loop and take the variables sum and maxVal.

• Use another for loop to iterate over the range of 60 subarrays, because beyond 60 subarrays, condition 2 will never be false.

• Add elements to sum and take the maximum value in maxVal.

• If sum is even and 2 * maxVal > sum, incrementing the count as condition 2 is not satisfied.

• Both loops return count at the end.

• Function findSubarrays(int arr1[], int len1) accepts an input array and its length, and returns the number of subarrays that meet the above two conditions.

• Use a prefix array to count the number of subarrays that only meet condition 1.

• Use a for loop to traverse the array and set each element __builtin_popcountll(arr1[i]) This is the number of bits set in it.

• Use a for loop to populate the prefix array and set prefix[i] = prefix[i] prefix [i - 1] except for the first element.

• Calculate the odd and even values ​​in the prefix array.

• Set tmp1 = ( oddcount * (oddcount-1) )/2 and tmp2= ( Evencount * (evencount-1) )/2 and take the result as the sum of the two.

• The result will be the sum of subarrays that satisfy condition 1 only.

• Print the results.

• Now update the result with result=result - removeSubarr( arr1, len1).

• The result now contains subarrays that satisfy both conditions.

• Print the results again.

Example

#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int removeSubarr(int arr[], int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      int sum = 0;
      int maxVal = 0;

      for (int j = i; j < min(len, i + 60); j++){
         sum = sum + arr[j];
         maxVal = arr[j] > maxVal ? arr[j]: maxVal;

         if (sum % 2 == 0){
            if( 2 * maxVal > sum)
               { count++; }
         }
      }
   }
   return count;
}
int findSubarrays(int arr1[], int len1){
   int prefix[len1];
   int oddcount, evencount;
   int result;
   for (int i = 0; i < len1; i++)
   { arr1[i] = __builtin_popcountll(arr1[i]); }

   for (int i = 0; i < len1; i++){
      prefix[i] = arr1[i];
      if (i != 0)
         { prefix[i] = prefix[i] + prefix[i - 1]; }
      }
      oddcount = evencount = 0;
      for (int i = 0; i < len1; i++){
         if (prefix[i] % 2 == 0)
            { evencount = evencount +1; }
         else
            { oddcount = oddcount +1; }

      }
      evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

Output

If we run the above code it will generate the following output

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3

The above is the detailed content of In C++, maximize the number of subarrays with zero XOR. For more information, please follow other related articles on the PHP Chinese website!