Problem: BINFUN

If you think about what the function is really doing,

XplusY = X left shifted by length of binary representation of Y + Y

YplusX = Y left shifted by length of binary representation of X + X

And then maximizing, XplusY - YplusX

By length of binary representation I mean,

The number of bits upto the MSB

6-> 110, length = 3

12-> 1100, length = 4

let n = length of binary representation of X

let m = length of binary representation of Y

We have to maximize, X * 2^m + Y - (Y * 2^n + X)

=> X * (2^m-1) - Y * (2^n - 1)

To maximize this, notice that n and m can only be in range [1, 30]

For a fixed (n,m) we can maximize this by taking the maximum X (having n bits) and minimum Y (having m bits). Do this for every (n,m) pair.

Reference

Ah!! I was too closeâ€¦ btw, nice explaination.

can u please give some counter test case where â€śhttps://www.codechef.com/viewsolution/36019868â€ť fails ?

1 3 4 5

Your output: 7

Correct output: 9 (using 3 and 4)

1

5

10 7 8 9 5

Ans is 49

```
void solve(){
int n;
cin >> n;
ll a[n];
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
ll X[2] = {noOfBits(a[0]), a[0]};
ll Y[2] = {noOfBits(a[0]), a[0]};
// X*(2^n - 1) - Y*(2^m - 1)
// find smallest m -> with biggest X
// find biggest n -> with smallest Y
for (int i = 1; i<n; i++) {
int temp = noOfBits(a[i]);
if (temp < X[0] ) {
X[0] = temp;
X[1] = a[i];
}
else if (temp == X[0]) {
if (a[i] > X[1] ) {
X[1] = a[i];
}
}
if (temp > Y[0] ) {
Y[0] = temp;
Y[1] = a[i];
}
else if (temp == Y[0]) {
if (a[i] < Y[1] ) {
Y[1] = a[i];
}
}
}
cout << (X[1] * ((1<<Y[0]) - 1)) - (Y[1] * ((1<<X[0]) - 1)) << "\n";
}
```

I am choosing biggest X with smallest â€śmâ€ť bits and vice-versa for Y.

Whatâ€™s wrong with this?

Hello @gajrajgchouhan.

Considering the expression - X*(2^n - 1) - Y*(2^m - 1) , you are maximising (2^n-1) and minimising (2^m-1), which doesnâ€™t necessarily maximise the expression before.

A simple example to counter your approach is with integers - 2, 6;

Binary Representation of 2,6 is 10,110 respectively.

BinaryConcatenation(2,6) = (10110) - (11010) = -4

BinaryConcatenation(6,2) = (11010) - (10110) = 4

Your approach gives -4 as result, but the maximum value would be 4.

Hope this was helpful to you.

Thank you bro