We have an array A (say [1,2,3])
. We need to find the XOR(^)SUM of all pairs of integers in the array.
Though this can easily be done in O(n^2)
but how can i improve the complexity of the solution ?
E.g for the above array , A, the answer would be (1^2)+(1^3)+(2^3) = 6
Thanks.
The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element. For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4 , and the XOR sum of [3] is equal to 3 .
Approach: In order to find the XOR of all elements in the array, we simply iterate through the array and find the XOR using '^' operator.
You can separate the calculation to do one bit at a time.
For example, look at the rightmost bit of all the numbers in the array. Suppose that a
numbers have a rightmost 0-bit, and b
numbers have a 1-bit. Then out of the pairs, a*b
of them will have 1 in the rightmost bit of the XOR. This is because there are a*b
ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute a*b
towards the total of all the XORs.
In general, when looking at the n
th bit (where the rightmost bit is the 0th), count how many numbers have 0 (call this an) and how many have 1 (call this bn). The contribution towards the final sum will be an*bn*2n. You need to do this for each bit and sum all these contributions together.
This can be done in O(kn) time, where k
is the number of bits in the given values.
Here is a jsFiddle confirming interjay's answer which does the calculation using both methods O(N^2) vs O(Nk):
var list = [1,2,2,3,4,5]
function xorsum_on2( a )
{
var sum = 0
for( var i=0 ; i<a.length ; ++i )
for( var j=i+1 ; j<a.length ; ++j )
sum += a[i]^a[j]
return sum
}
// This sets all elements of a to 0
function xorsum_onk( a )
{
var allzeroes;
var sum = 0;
var power = 0;
do {
allzeroes = true;
var bitcount = [0,0];
for( var i=0 ; i<a.length ; ++i )
{
bitcount[a[i]&1]++;
a[i] >>= 1;
if( a[i] ) allzeroes = false;
}
sum += (bitcount[0]*bitcount[1]) << power++;
} while( !allzeroes );
return sum;
}
var onk = document.getElementById("onk")
var on2 = document.getElementById("on2")
on2.innerHTML = xorsum_on2(list)
onk.innerHTML = xorsum_onk(list)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With