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

Question 1

Click here to Practice

1.1

Question 2

2.12.22.3

ADD COMMENTlink 15 days ago John 450 • updated 11 days ago Ujjwal Srivastava 160
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 >> 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;
ADD COMMENTlink 11 days ago Ujjwal Srivastava 160

Login before adding your answer.

Similar Posts
Loading Similar Posts