Loading Similar Posts

Entering edit mode

**Overview**

- We have
**N**queries of forms X, L, and R. - We have to find the
**maximum value of X^Y**where**Y belongs to [L,R].**

**Solution**

- We basically need to find a suitable value of Y that results in a
**maximum value of X^Y**. - We need Y to have complementary bits to that of X to have the maximum value.
We will iterate from the

**largest set bit in R**to the lowest**(0th Bit)**. The following two cases can arise for each bit:If the

**bit is not set, i.e. 0 in X**, we will try to**set it in Y**. If setting this bit to 1 results in Y exceeding R, then we will not set it.If the

**bit is set, i.e. 1 in X**, then we will try not to set it in Y.- If the
**current value of Y is already greater than or equal to L**, then we can ignore the bit i.e not set the bit in Y. - In the other case,
**we will check if setting all of the next bits is enough to keep Y >= L**. If not, then we are required to set the current bit.

- At last, when we have iterated over all the bits, we will have our required value of Y hence the maximum value of X^Y.

**Code**

```
ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
ll x, l, r;
cin >> x >> l >> r;
ll y = 0;
for (ll j = 30; j >= 0; j--)// iterate from largest to smallest bit
{
ll val = (1ll << j);
if (x & val)// if the current bit is set in x
{
if (y + val - 1 < l)// Even if after setting all the next bits, the value of y remains less than r than we have to set the current bit
{
y += val;// we have to forcefully set the current bit
}
}
else// if the current bit is not set in x
{
if (y + val <= r)// if setting the current bit doesn't exceeds r
{
y += val;// set the current bit
}
}
}
cout << (x ^ y) << endl;
}
return;
```

Loading Similar Posts