我们得到一个包含整数值的数组 Arr[]。目标是找到 XOR 为 0 的最大子数组数。任何子数组的位都可以交换任意次数。
注意：- 1<=Arr[i]<=10 18
为了通过交换位使任何子阵列的 XOR 为 0，必须满足两个条件：-
如果从左到右范围内的设置位数为偶数。
对于任何给定范围的位总和 <= 2（设置位中的最大数）
让我们看看这个的各种输入输出场景 -
在 -Arr[] = { 1,2,5,4 }
出 -
仅满足第一个条件的子数组：4
满足两个条件的子数组：3
在 - Arr[] = { 3,7,2,9 }
出 -
仅满足第一个条件的子数组：6
满足两个条件的子数组：3
在这种方法中，我们观察到，为了通过交换位使任何子阵列的 XOR 为 0，必须满足两个条件：- 如果从左到右范围内的设置位数量是偶数或对于任何给定范围的位总和 <= 2（设置位中的最大数）
取输入数组 Arr[] 并计算其长度。
函数 removeSubarr(int arr[], int len) 返回不满足条件 2 的子数组的数量。
取初始计数为 0。
使用 for 循环迭代数组并取变量 sum 和 maxVal。
使用另一个 for 循环在 60 个子数组的范围内进行迭代，因为超过 60 个，条件 2 永远不会为假。
将元素添加到 sum 并在 maxVal 中取最大值。
如果 sum 为偶数且 2 * maxVal > sum 则增加 count 作为条件 2 不满足。
在两个循环结束时返回计数。
函数 findSubarrays(int arr1[], int len1) 接受一个输入数组及其长度，并返回满足上述两个条件的子数组的计数。
取一个前缀数组来计算仅遵循条件 1 的子数组的数量。
使用 for 循环遍历数组并使用 __builtin_popcountll(arr1[i]) 设置每个元素，这是其中设置的位数。
使用 for 循环填充前缀数组并设置 prefix[i] = prefix[i] + prefix[i - 1] 其中除了第一个元素。
计算前缀数组中的奇数和偶数值。
设置 tmp1= (oddcount * (oddcount-1) )/2 和 tmp2= ( evencount * (evencount-1) )/2 并将结果作为两者的总和。
结果将是仅满足条件 1 的子数组的总和。
打印结果。
现在用 result=result 更新结果 - removeSubarr(arr1, len1)。
现在结果包含满足这两个条件的子数组。
再次打印结果。
#include <bits/stdc++.h>
using namespace std;
// 计算不满足条件 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 << "仅满足第一个条件的子数组： "<<result << endl;
cout << "满足两个条件的子数组： ";
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;
}输出结果如果我们运行上面的代码，它将生成以下输出
仅满足第一个条件的子数组： 4 满足两个条件的子数组： 3