### HuTao_Oya_OyaOya's blog

By HuTao_Oya_OyaOya, history, 5 weeks ago,

Problem in short : Find sum of XOR of all subarrays of size>1 in the given array of size n in linear time.

My idea is to get the prefix sum array of XORs and now the problem is reduced to finding XOR between all possible pairs in prefix XOR array.

I tried for hours to debug the code but couldn't figure out what did I do wrong. Any help would be greatly appreciated.

Old Code

UPD :

AC
What was the problem earlier ?
 » 5 weeks ago, # |   0 Your approach is right but code is wrong.
 » 5 weeks ago, # |   0 Can't you use segment tree to solve it in O(nlogn) ?
•  » » 5 weeks ago, # ^ |   0 No.
•  » » 5 weeks ago, # ^ |   0 yes, you can
 » 5 weeks ago, # |   0 Solution/****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ // C++ program to find the sum of XOR of // all subarray of the array #include #include using namespace std; // Function to calculate the sum of XOR // of all subarrays int findXorSum(int arr[], int n) { // variable to store // the final sum int sum = 0; // multiplier int mul = 1; for (int i = 0; i < 30; i++) { // variable to store number of // sub-arrays with odd number of elements // with ith bits starting from the first // element to the end of the array int c_odd = 0; // variable to check the status // of the odd-even count while // calculating c_odd bool odd = 0; // loop to calculate initial // value of c_odd for (int j = 0; j < n; j++) { if ((arr[j] & (1 << i)) > 0) odd = (!odd); if (odd) c_odd++; } // loop to iterate through // all the elements of the // array and update sum for (int j = 0; j < n; j++) { sum += (mul * c_odd); if ((arr[j] & (1 << i)) > 0) c_odd = (n - j - c_odd); } // updating the multiplier mul *= 2; } for (int j = 0; j < n; j++) sum -= arr[j]; // returning the sum return sum; } // Driver Code int main() { //int arr[] = { 1, 3, 2 }; int arr[] = {2, 5, 6, 5, 2, 1, 7}; int n = sizeof(arr) / sizeof(arr[0]); cout << findXorSum(arr, n); return 0; } Code from, i just subtract the sum of all subarrays of 1 element
•  » » 5 weeks ago, # ^ |   0 Hello Drakengard based pfp
 » 5 weeks ago, # |   +3
 » 5 weeks ago, # |   0 no thanks to me ?
•  » » 5 weeks ago, # ^ |   0 No
 » 5 weeks ago, # |   0 just solved it :3 very cute problem! the idea is to prefix sum on the bits of the number themselves, then we just count the number of subarrays on the bits such as the number of 1's is odd without the number it self, can be done in O(n) per bit so O(nlogn), again very cute and unexpected/smart solution from my side :D
 » 5 weeks ago, # |   0 To find XOR between every pair you can sum the contribution for each bit individually.First We will make a array cnt[i] = #Number of elements with i-th bit on(equal to one).For i-th bit we add $2^{i} * cnt[i] * (n - cnt[i])$ because i-bit will be on when there is exactly one number have that bit on.