Need Help to solve XXOR

help
1

I have written a code for this problem XXOR, But got WA after submission.
Approach: I am storing no of 1’s for a bit_location from 0 to index in one[index][bit_location]. similarly storing no of 0’s for a bit_location from 0 to index in zero[index][bit_location]. Now for each query, for each and every bit_location , i am calculating no of one and no of zero using prefix sum and if no of zero > no of one then i am setting that bit_location of ans to 1.

int main(){
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	vector<long long int>vec;
	long long int test,q,n,a[MAX],one[MAX][32],zero[MAX][32],l,r,z,o,ans;
	
	cin >> n >> q;
	for(int i=0;i<n;i++)
		cin >> a[i];


	for(int bit_loc = 0;bit_loc < 31;bit_loc++){
		for(int i=0;i<n;i++){
			if(a[i] & (1<<bit_loc)){
				if(i == 0){
					one[i][bit_loc] = 1;
					zero[i][bit_loc] = 0;
					continue;
				}
				one[i][bit_loc] = one[i-1][bit_loc]+1;
				zero[i][bit_loc] = zero[i-1][bit_loc];
			}else{
				if(i == 0){
					one[i][bit_loc] = 0;
					zero[i][bit_loc] = 1;
					continue;
				}
				zero[i][bit_loc] = zero[i-1][bit_loc]+1;
				one[i][bit_loc] = one[i-1][bit_loc];
			}
		}
	}

	

	ans = 0;
	while(q--){
		cin >> l >> r;
		l--;
		r--;
		for(int bit_loc = 0;bit_loc < 31;bit_loc++){
			if(l == 0){
				z = zero[r][bit_loc];
				o = one[r][bit_loc];
			}else{
				z = zero[r][bit_loc]-zero[l-1][bit_loc];
				o = one[r][bit_loc]-one[l-1][bit_loc];
			}
			
			if(z > o){
				ans = (ans | (1 << bit_loc));
				
			}
		}
		
		cout << ans << endl;
	}
2

inside the last while loop
while(q--)
You have to reassign ans=0;
Otherwise the ans you got in the previous query would be used.

1 Like
3

Thank you.I was unable to figure out why it’s not working , although i knew that my algo is right.Thank you so much. :pray:

1 Like
4

inside the last while loop
while(q--)
You have to reassign `ans=0;