Question: Pine Labs, Recently Asked On-Campus Assessments in IITs, October, 2022
0
Entering edit mode

# Question 2

1
Entering edit mode

## Question 1

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 &gt;&gt; n;
for (ll i = 0; i &lt; n; i++)
{
ll x, l, r;
cin &gt;&gt; x &gt;&gt; l &gt;&gt; r;
ll y = 0;
for (ll j = 30; j &gt;= 0; j--)// iterate from largest to smallest bit
{
ll val = (1ll &lt;&lt; j);
if (x &amp; val)// if the current bit is set in x
{
if (y + val - 1 &lt; 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 &lt;= r)// if setting the current bit doesn't exceeds r
{
y += val;// set the current bit
}
}
}
cout &lt;&lt; (x ^ y) &lt;&lt; endl;
}
return;
``````