数组中所有成对的整数和的异或 [英] Xor of all pairwise sums of integers in an array

问题描述

我们有一个数组 A ，例如 [1、2、3] .我想找到数组中所有整数对的SUM的XOR.
尽管可以通过遍历所有对来轻松地在 O(n ^ 2)(其中 n 是数组的大小)中完成此操作，但我想改进解决方案的时间复杂度?任何可以提高时间复杂度的答案都是很好的.
例如.对于上面的示例数组 A ，答案将是(1 + 2)^(1 + 3)^(2 + 3)= 2 .由于成对元素是(1,2)，(1,3)，(2,3)和 3 ^ 4 ^ 5 = 2 .

We have an array A for example [1, 2, 3]. I want to find the XOR of the SUM of all pairs of integers in the array.
Though this can easily be done in O(n^2) (where n is the size of the array) by passing over all of the pairs, I want to improve the time complexity of the solution? Any answer that improves the time complexity would be great.
E.g. for the above example array, A, the answer would be (1+2)^(1+3)^(2+3) = 2. Since the pairwise elements are (1,2), (1,3), (2,3), and 3 ^ 4 ^ 5 = 2.

推荐答案

这是我对至少一位作者的 用于 O(n * log n * w)解决方案，其中 w 是最大和的位数.

Here's my understanding of at least one author's intention for an O(n * log n * w) solution, where w is the number of bits in the largest sum.

这个想法是一次检查每个位的贡献.由于我们只对求和中的第 k 位是否感兴趣，可以在任何一次迭代中进行设置，因此我们可以删除数字中包含较高位的所有部分，并将它们取模为 2 ^(k +1).

The idea is to examine the contribution of each bit one a time. Since we are only interested in whether the kth bit in the sums is set in any one iteration, we can remove all parts of the numbers that include higher bits, taking them each modulo 2^(k + 1).

现在，必须将第 k 个位置位的总和位于间隔 [2 ^ k，2 ^(k + 1))和 [2 ^(k + 1)+ 2 ^ k，2 ^(k + 2)-2] .因此，我们对输入列表进行排序(取模 2 ^(k + 1))，对于每个左求和，我们递减一个指针到两个间隔中每个间隔的末尾，然后对相关的开始进行二进制搜索索引.

Now the sums that would necessarily have the kth bit set lie in the intervals, [2^k, 2^(k + 1)) and [2^(k+1) + 2^k, 2^(k+2) − 2]. So we sort the input list (modulo 2^(k + 1)), and for each left summand, we decrement a pointer to the end of each of the two intervals, and binary search the relevant start index.

这里的JavaScript代码具有与蛮力的随机比较，以证明其有效(可以轻松转换为C或Python):

Here's JavaScript code with a random comparison to brute force to show that it works (easily translatable to C or Python):

// https://stackoverflow.com/q/64082509
// Returns the lowest index of a value
// greater than or equal to the target
function lowerIdx(a, val, left, right){
  if (left >= right)
    return left;
  mid = left + ((right - left) >> 1);
  if (a[mid] < val)
    return lowerIdx(a, val, mid+1, right);
  else
    return lowerIdx(a, val, left, mid);
}

function bruteForce(A){
  let answer = 0;
  for (let i=1; i<A.length; i++)
    for (let j=0; j<i; j++)
      answer ^= A[i] + A[j];
  return answer;
}
  
function f(A, W){
  const n = A.length;
  const _A = new Array(n);
  let result = 0;

  for (let k=0; k<W; k++){
    for (let i=0; i<n; i++)
      _A[i] = A[i] % (1 << (k + 1));
    _A.sort((a, b) => a - b);

    let pairs_with_kth_bit = 0;
    let l1 = 1 << k;
    let r1 = 1 << (k + 1);
    let l2 = (1 << (k + 1)) + (1 << k);
    let r2 = (1 << (k + 2)) - 2;
    let ptr1 = n - 1;
    let ptr2 = n - 1;

    for (let i=0; i<n-1; i++){
      // Interval [2^k, 2^(k+1))
      while (ptr1 > i+1 && _A[i] + _A[ptr1] >= r1)
        ptr1 -= 1;
      const idx1 = lowerIdx(_A, l1-_A[i], i+1, ptr1);
      let sum = _A[i] + _A[idx1];
      if (sum >= l1 && sum < r1)
        pairs_with_kth_bit += ptr1 - idx1 + 1;

      // Interval [2^(k+1)+2^k, 2^(k+2)−2]
      while (ptr2 > i+1 && _A[i] + _A[ptr2] > r2)
        ptr2 -= 1;
      const idx2 = lowerIdx(_A, l2-_A[i], i+1, ptr2);
      sum = _A[i] + _A[idx2]
      if (sum >= l2 && sum <= r2)
        pairs_with_kth_bit += ptr2 - idx2 + 1;
    }

    if (pairs_with_kth_bit & 1)
      result |= 1 << k;
  }
  return result;
} 
 
var As = [
  [1, 2, 3], // 2
  [1, 2, 10, 11, 18, 20], // 50
  [10, 26, 38, 44, 51, 70, 59, 20] // 182
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(`DP, brute force: ${ f(A, 10) }, ${ bruteForce(A) }`);
  console.log('');
}

var numTests = 500;

for (let i=0; i<numTests; i++){
  const W = 8;
  const A = [];
  const n = 12;
  for (let j=0; j<n; j++){
    const num = Math.floor(Math.random() * (1 << (W - 1)));
    A.push(num);
  }

  const fA = f(A, W);
  const brute = bruteForce(A);
  
  if (fA != brute){
    console.log('Mismatch:');
    console.log(A);
    console.log(fA, brute);
    console.log('');
  }
}

console.log("Done testing.");

这篇关于数组中所有成对的整数和的异或的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！