Problem Description
Given an array of N integers, find the sum of xor of all pairs of numbers in the array.
geeksforgeeks
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution{
// Function for finding maximum and value pair
public long sumXOR (int arr[], int n) {
long sum = 0;
for(int i=0; i<=31; i++){
long c = 0; //Count of number of set bits at position i
for(int j=0; j<n; j++){
if(checkSetAtPosition(arr[j], i)) c++; //Increase count if the bit is set at position i
}
//The number of pairs which can be made with numbers which have bits set at pos i AND numbers which have bit unset at pos i = c*(n-c)
//Every pair will contribute 2^i where i is its position. 2^1 === (1<<i)
//So, we add the contribution on this position to the total sum
sum = sum + c*(n-c)*(1<<i);
}
return sum;
}
public boolean checkSetAtPosition(int n, int i){
n = n>>i;
return (n&1)==1;
}
}