CODEWITHSUNDEEP
algorithmxor
Francois Vogel
Francois Vogel

Reputation: 33

sum of XOR on all combinations of values of two subsets

Let's say i have two array of integers a and b with n integers each. I want to know the sum of the xor on all combinations of two integers in the two different subsets.

for example, if n == 3: i want to know the value of:

a1^b1 + a1^b2 + a1^b3 + a2^b1 + a2^b2 + a2^b3 + a3^b1 + a3^b2 + a3^b3

is there a way to this efficiently do this in a similar way as with + and x

i.e. 1*2 + 1*3 + 2*2 + 2*3 = (1+2)*(2+3)

Upvotes: 0

Views: 307

Answers (2)

AYUSH PATEL
AYUSH PATEL

Reputation: 1

class Solution{
    public:
    // Returns sum of bitwise OR
    // of all pairs
    long long int sumXOR(int arr[], int n)
    {
         
    long long int ans = 0;

    for (int i = 0; i < 32; i++)
    {
        int sethai = 0;
        for (int j = 0; j < n; j++)
        {
            if (arr[j] & (1 << i))
            {
                sethai++;
            }
        }
        ans += (long long)((long long)sethai * (n - (long long)sethai)) * (1 << i);
    }

    return ans;
        
    }
};

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59174

There is a formula that works if there is only one non-zero value in the arrays. Because of this, you can do this one bit-value at a time, and then add up the results for each bit-value.

If you know that a contains x ones and n-x zeros, and b contains y ones and n-y zeros, then every a^b is either 1 or 0, and the number of 1s is exactly x * (n-y) + y * (n-x).

If you isolate the 1 bits, in the subsets, then you can calculate how many 1 bits are set in the XOR pairs. Similarly if you isolate the 2 bits, you can calculate how many 2 bits are set in the XOR pairs. Adding the results for each bit value give the final answer:

int total = 0;
for (int bit=1; bit>0 && (bit  < a.length || bit < b.length); bit<<=1) {
    int acount = 0;
    for (int val : a) {
        acount += val & bit;
    }
    acount /= bit;
    int bcount = 0;
    for (int val: b) {
        bcount += val & bit;
    }
    bcount /= bit;
    total += bit * ( acount * (b.length-bcount) + bcount * (a.length-acount) );
}

Upvotes: 2

Related Questions