As Rajat was getting bored in his holidays, he asked his friend Viraj for a challenging problem. Viraj gave him a sequence of integers X1, X2, …, XN. In each of the subsequent Z queries, he was given two parameters P and Q. Viraj asked Rajat to find the smallest integer C such that the value of (XP xor C) + (XP+1 xor C) + … + (XQ xor C) is maximum possible. 0 ≤ C < 231
Note: xor represents bitwise xor operation.
Input
First line contains two space-separated integers N and Z
Second line contains N space-separated integers X1, X2, …, XN.
Each of the next Z lines contains two space-separated integers P and Q.
Constraints
1 ≤ N ,Z ≤ 10^5
0 ≤ Xi < 231 ,for each valid i
Output
For each query, print a single integer — the minimum value of C.
Sample Input :
5 3
20 11 18 2 13
1 3
3 5
2 4
Sample Output:
2147483629
2147483645
2147483645
Iam Getting correct output for 1 and 2 but wrong output for third sample test case.
Here is my code:
#include <bits/stdc++.h>
using namespace std;
int reverseBits( int n)
{
int rev = 0;
while (n > 0)
{
rev <<= 1;
if (n & 1 == 1)
rev ^= 1;
n >>= 1;
}
return rev;
}
int main()
{
int n,z;
cin>>n>>z;
vector a(n,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
vector ans(32,1);
for( int j=0;j<z;j++)
{
int p,q,res=0;
cin>>p>>q;int m=0;
for( int h=p-1;h<q;h++)
{
int temp;
if (a[h] == 0)
temp = 0;
else
{
temp = 0;
int k = a[h];
while (k != 0)
{
k = k / 2;
temp++;
}
}
m = max(m,temp);
res = res ^ a[h];
}
int ans= 2147483647;
for (int i = 0; i < m; i++)
res = (res ^ (1 << i));
ans = ans^res;
cout<<ans<<endl;
}
}