从数组中选择一个元素，以便在XOR数组中的所有元素之后最大化和

Question

给你一个数组A。你必须从这个数组中选择一个元素，比如说Ak，并形成一个新的数组B，这样Bi = Ai^Ak。(^表示按位异或)。

现在数组的分数是B的所有元素之和。

任务是查找数组得分最大的元素。

例子-

如果A= 15,11,8

我们选择Ak = 15，那么B就是0,4,7。得分将是0+4+7 = 11，这是我们通过选择任何元素作为Ak可以得到的最大值。

另一个例子-

如果A= 11,12,13,14,15，最大可能的score=22。

如何解决这个问题，选择一个能得到最大分数的元素。

如何解决这一问题，或如何处理这些问题？

Answer 1

许多xor算法问题的答案是一点一点地工作。在这里，如果对每个位位置计算具有该位集的数组元素的数量(顺便告诉您有多少个数组元素没有通过减去数组长度来设置该位)，则可以通过考虑每个可能的位所贡献的部分和来快速计算任何X的X。这种计算和的方法取决于数组中最大数字的位宽，而不是数组的长度。

一旦您这样做了，您可以简单地遍历数组并找到使和最大化的元素。

如果你做得对，那么算法是O(NW)，其中N是输入数组的长度，W是最小的数，使得每个输入数都符合一个W位整数。它将使用O(W)额外的存储空间。(通常，这些算法问题限制了输入的大小，因此它们适合于int32或int64，因此W将为32或64)。