Help me in solving XORGAND problem

help
,
1

My issue

My code

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

int get_msb_pos(int num){
    int count=0;
    while(num>0){
        num= num/2;
       count++; 
    }
    
    return count;
}

void solve(){
        
   int n;
   cin>>n;
   
   int a[n]; for(int i=0; i<n; i++) cin>>a[i];
   
   int q;
   cin>>q;
   
   while(q--){
       int l,r,x;
       
       cin>>l>>r>>x;
       int count=0;
        int v = get_msb_pos(x) ;
       for(int i=l-1; i<r; i++){
       int p = get_msb_pos(a[i]);
       
     if(v!=p) count++;
       }
     
      cout<<count<<endl; 
   }
 
}

signed main() {
    
ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int t; cin>>t;
   while(t--)
       
solve();

       


}

Problem Link: XORGAND Problem - CodeChef

2

@sh_reya
your logic is correct but u can’t iterate from l to r in the q loop this is giving u tle.
so to remove it u can precompute for all values of x outside the q loop which is 32 at max according to constraints and store it in some data structure to use it in q loop .

3

yes, thank you! i got it. it can be computed using prefix sum method.

1 Like