Thursday, 8 November 2018

Chef and Easy Problem CodeChef March Challenge solution in C++ using bitset

 Problem : https://www.codechef.com/MARCH18B/problems/XXOR/


 Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;

int main() {

    long long int n,q;
    cin>>n>>q;
    long long int temp,bc[n];
    bitset<31> bin[n];
    for(long long int i=0;i<n;i++)
    {
        cin>>temp;
        bin[i]=temp;
        bc[i]=floor(log2(temp))+1;
    }
    //cout<<bin[0];
     while(q--)
    {
        long long int a1,b1;
        bitset<31> b;
        b.set();
        cin>>a1>>b1;
        a1--;
        b1--;
        long long int max=bc[a1];
        for(long long int i=a1+1;i<=b1;i++)
        {
            if(max<bc[i])
                max=bc[i];
        }
      
        for(long long int j=max-1;j>=0;j--)
        {
            long long int c0=0,c1=0;
            for(long long int i=a1;i<=b1;i++)
            {
                if(bin[i][j]==1)
                    c1++;
                else
                    c0++;
            }
            if(c1>=c0)
            b.reset(j);
        }
        cout<<b.to_ulong() << '\n';
    }
    return 0;
}