数组中每个无序对的成对和的异或 [英] XOR of pairwise sum of every unordered pairs in an array
问题描述
问题描述:给定长度为N的数组arr []，任务是找到该数组的每个可能无序对的成对和的异或.
Question Description : Given an array arr[] of length N, the task is to find the XOR of pairwise sum of every possible unordered pairs of the array.
我使用此帖子中所述的方法解决了这个问题.
I solved this question using the method described in this post.
我的代码:
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"表示).
Code Descrption : I am finding out at each bit, whether our answer will have that bit set ort not. So to do this for each bit-position, I find the count of all the numbers which have a set bit at the position(represeneted by 'o' in the code) and the count of numbers having un-set bit at that position(represented by 'z').
现在，如果我们将这些数字配对(具有置位和未置位的数字在一起，那么我们将在它们的总和中得到一个置位(因为我们需要对所有对和进行异或).
Now if we pair up these numbers(the numbers having set bit and unset bit together, then we will get a set bit in their sum(Because we need to get XOR of all pair sums).
包括"prev"因数以说明结转位.现在我们知道，只有在我们进行异或运算时，如果设置的位数为奇数"，答案才会在当前位置具有一个设置的位.
The factor of 'prev' is included to account for the carry over bits. Now we know that the answer will have a set bit at current position only if the number of set bits are 'odd' as we are doing an XOR operation.
但是我没有得到正确的输出.谁能帮我
But I am not getting correct output. Can anyone please help me
测试用例:
- n = 3，a [] = {1,2,3} =>(1 + 2)^(1 + 3)^(2 + 3)
=>3 ^ 4 ^ 5 = 2
=> 3 ^ 4 ^ 5 = 2
=>输出:2
=> Output : 2
-
n = 6
n = 6
a [] = {1 2 10 11 18 20}
a[] = {1 2 10 11 18 20}
输出:50
n = 8
a [] = {10 26 38 44 51 70 59 20}
a[] = {10 26 38 44 51 70 59 20}
输出:182
约束:2< = n< = 10 ^ 8
Constraints : 2 <= n <= 10^8
此外，在这里我们需要考虑无序对而不是有序对.
Also, here we need to consider UNORDERED PAIRS and not Ordered Pairs for the answer
PS:我知道之前也有人问过同样的问题，但是我无法在评论中这么详细地解释我的问题，所以我创建了一个新帖子.我是新来的，请原谅我，并给我您的反馈意见:)
PS : I know that the same question has been asked before but I couldn't explain my problem with this much detail in the comments so I created a new post. I am new here, so please pardon me and give me your feedback :)
推荐答案
我怀疑您在帖子中提及的想法缺少重要的细节，如果它可以完全以所述的复杂性运行的话.(如果该作者希望进一步阐明他们的方法，我将很高兴更好地理解和纠正.)
I suspect that the idea in the post you referred to is missing important details, if it could work at all with the stated complexity. (I would be happy to better understand and be corrected should that author wish to clarify their method further.)
这是我对至少一个作者对 O(n)的意图的理解.* log n * w)解决方案，其中 w 是最大和的位数，以及JavaScript代码以及与蛮力的随机比较，以证明其有效(容易可翻译为C或Python).
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, as well as JavaScript code with a random comparison to brute force to show that it works (easily translatable to C or Python).
这个想法是一次检查每个位的贡献.由于在任何一次迭代中，我们仅对总和中的第
The idea is to examine the contribution of each bit one a time. Since in any one iteration, we are only interested in whether the kth bit in the sums is set, we can remove all parts of the numbers that include higher bits, taking them each modulo 2^(k + 1).
现在，在第 [2 ^ k，2 ^(k + 1))个区间中，必须设置第位和第 k 位的总和 k 位最高)和 [2 ^(k + 1)+ 2 ^ k，2 ^(k + 2)-2] (当我们有同时设置了第(k + 1)位).因此，在迭代过程中，我们为每个位排序输入列表(对 2 ^(k + 1)取模)，对于每个左求和，我们将指针递减到两个间隔中每个间隔的末尾，然后二进制搜索相关的起始索引.
Now the sums that would necessarily have the kth bit set are in the intervals, [2^k, 2^(k + 1)) (that's when the kth bit is the highest) and [2^(k+1) + 2^k, 2^(k+2) − 2] (when we have both the kth and (k+1)th bits set). So in the iteration for each bit, 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.
// 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屋！
