Help in Problem E : XOR Sigma

#	User	Rating
1	tourist	3947
2	ecnerwala	3654
3	jiangly	3627
4	jqdai0815	3620
5	orzdevinwang	3612
6	Benq	3586
7	Radewoosh	3582
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3474

#	User	Contrib.
1	awoo	163
2	maomao90	160
3	adamant	156
4	atcoder_official	154
5	maroonrk	152
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	145
10	cry	144

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.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    vector<int>pref(n); pref[0]=v[0];
    for(int i=1;i<n;i++) pref[i]=pref[i-1]^v[i];
    for(int i=0;i<n;i++) v[i]=pref[i];
    ll res = 0;
    vector<vector<int>>set(n,vector<int>(30));
    vector<vector<int>>unset(n,vector<int>(30));
    for(int i=0;i<30;i++) {
        if((v[0]&(1<<i))!=0) set[0][i]=1;
        else unset[0][i]=1;
    }
    for(int i=1;i<n;i++) {
        for(int j=0;j<30;j++) {
            set[i][j] = set[i-1][j]; unset[i][j] = unset[i-1][j];
            if((v[i]&(1<<j))!=0) set[i][j]++;
            else unset[i][j]++;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<30;j++){
            if((v[i]&(1<<j))!=0) res+=unset[i-1][j]*(1<<j);
            else res+=set[i-1][j]*(1<<j);
        }
    }
    cout<<res;
}

Comments (5)

Write comment?

StellarSpecter

2 hours ago, # |

Your approach is right but code is wrong.

→ Reply

vaibhav2740

Can't you use segment tree to solve it in O(nlogn) ?

118 minutes ago, # ^ |

No.

xQConqueror

77 minutes ago, # |

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 <iostream>
#include <vector>
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

srinivas1999

32 minutes ago, # |

https://www.geeksforgeeks.org/sum-of-xor-of-all-subarrays

HuTao_Oya_OyaOya's blog