如何找到最长的子数组，使其xor具有偶数奇偶性

Question

我在O(n^2(复杂性中找到了一个解决方案，如下所示：

但是，有什么方法可以降低它的时间复杂性吗？

这是仓功能

int bin(int n)
{
int i = 0;
while (n > 0)
{
if (n % 2 == 1)
i++;
n = n / 2;
}
return i;
}

这是主中的代码

for (int j = 0; j < n; j++)
{
int ans = a[j];
for (int k = j + 1; k < n; k++)
{
ans = ans ^ a[k];
if (bin(ans) % 2 == 0)
{
if (k - j + 1 > final)
{
final = k - j + 1;
}
}
}
}

Answer 1

注意两件事：

1. 两个元素的X或具有偶奇偶性当且仅当它们的奇偶性之和是偶的。

2. n个元素的Xor等于用第n个元素异或的n-1个元素的异或。

如果所有元素的奇偶校验和都是偶数，那么就完成了。数组本身是最长的。

如果不是，则可以同时遍历数组的两端，查找奇数奇偶校验字节。留下第一个这样的元素及其后面的其余元素的子阵列是最长的。完成。

注意，应该有这样的元素，否则和将是偶数。

Answer 2

具有偶奇偶校验的子阵列是由任意数量的偶数和偶数的奇数组成的序列。如果你的数组满足这个条件，那么你就完成了(O(n((。否则，找到一个最靠近前面[或后面]的奇数，并使子阵列经过[或在]该位置(O(n((。

这立即为您提供了子数组不能扩展的证据。