c++ - 数组中每个无序对的成对和的异或

Question

问题描述:给定一个长度为 N 的数组 arr[]，任务是找到数组中每个可能的无序对的两两和的异或。

我使用this中描述的方法解决了这个问题。发布。

我的代码:

int xorAllSum(int a[], int n)
{
    int curr, prev = 0;
    int ans = 0;
    for (int k = 0; k < 32; k++) {
        int o = 0, z = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] & (1 << k)) {
                o++;
            }
            else {
                z++;
            }
        }

        curr = o * z + prev;
        if (curr & 1) {
            ans = ans | (1 << k);
        }
        prev = o * (o - 1) / 2;
    }
    return ans;
}

代码描述:我在每一位上找出我们的答案是否会设置该位。因此，为了对每个位位置执行此操作，我找到在该位置具有设置位的所有数字的计数(在代码中由“o”表示)以及在该位置具有未设置位的数字的计数(由'z'表示)。

现在，如果我们将这些数字配对(将设置位和未设置位的数字放在一起，那么我们将在它们的和中得到一个设置位(因为我们需要对所有对和进行异或)。

包含“prev”因子以考虑结转位。现在我们知道，只有当我们进行异或运算时设置位的数量为“奇数”时，答案才会在当前位置有一个设置位。

但我没有得到正确的输出。谁能帮帮我

测试用例:

1. n = 3, a[] = {1, 2, 3} => (1 + 2) ^ (1 + 3) ^ (2 + 3)

=> 3^4^5=2

=> 输出:2

n = 6

a[] = {1 2 10 11 18 20}

输出:50

n = 8

a[] = {10 26 38 44 51 70 59 20}

输出:182

约束:2 <= n <= 10^8

此外，这里我们需要考虑无序对而不是有序对作为答案

PS:我知道以前也有人问过同样的问题，但我无法在评论中详细解释我的问题，所以我创建了一个新帖子。我是新来的，所以请原谅我并给我您的反馈:)

Answer 1

我怀疑 post you referred to 中的想法缺少重要的细节，如果它可以在规定的复杂性下工作的话。 (如果作者希望进一步阐明他们的方法，我很乐意更好地理解并得到纠正。)

这是我对至少一位作者的理解 intention对于 O(n * log n * w) 解决方案，其中 w 是最大和中的位数，以及与暴力随机比较的 JavaScript 代码强制证明它有效(可以轻松翻译为 C 或 Python)。

这个想法是每次检查每一位的贡献。由于在任何一次迭代中，我们只关心总和中的第 k 位是否已设置，因此我们可以删除包含较高位的数字的所有部分，将它们分别模 2 ^(k + 1).

现在，必须设置第 k 位的总和位于间隔 [2^k, 2^(k + 1)) 中(此时第 k 位是最高位)和 [2^(k+1) + 2^k, 2^(k+2) − 2](当我们有第 k 位和第 (k+1) 位集)。因此，在每个位的迭代中，我们对输入列表进行排序(模 2^(k + 1))，并且对于每个左被加数，我们递减一个指向两个区间末尾的指针，并二分查找相关的起始索引。

// 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.");