# PROBLEM LINK: Karunee’s Challenge

# DIFFICULTY:

SIMPLE.

# PREREQUISITES:

Greedy, Math, Bitmask , Bit Manipulation

# PROBLEM:

Given an integer **X** you need to output maximum possible integer **C** such that A*B=C, where X = A **opr** B.

# QUICK EXPLANATION:

By the property of **opr** given in question it is well clear that **opr** is bitwise **XOR** operator.

You would need basic XOR concept to understand this problem. The XORed result has two kind of bits in binary representation.

If i_{ith} bit is 0 in C then i_{ith} bit of both A and B should be either 0 or 1. And if i_{ith} bit is 1 in C then either one of A and B has i_{ith} bit set(1) and other has i_{ith} bit unset(0).

# EXPLANATION:

We will try to come up with some greedy approach to find A and B such that product can be maximized.

Since we need maximized product so we will always set i_{ith} bit = 1 in A and B whenever i_{ith} bit is 0 in C.

Now interesting case comes when i_{ith} bit is 1 in C. If you list put every possible combinations you will notice that the sum of A and B remains constant. And when sum of A and B is constant we get maximum product when A and B are closest to each other.

Eg A+B = 6.

Possible Combinations :

A B Product

1 5 5

2 4 8

3 3 9

So we get max product 9 when A and B are very close to each other.

So to make A and B close to each other, we apply greedy approach and it goes as follows :

For MSB set bit in C we will set that bit in A and for all the other set bit in C, we will make that bit set in B. So that A and B are close to each other and product maximises.

**Time Complexity:**

Time Complexity of this approach is **O(1)**. Since we have to work for only atmost 17 bits.

# ALTERNATE EXPLANATION:

Since we know value of A \leq N and B \leq N and constraints on N are quite small , an alternative approach can be to try out all values of B and check out its product with corresponding value of A.

**Time Complexity:** **O(N)**

# SOLUTIONS:

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
while (t--)
{
ll i, j, k, n, m;
cin >> n;
ll msb;
for (i = 17; i >= 0; i--)
if ((1 << i)&n)
{
msb = i;
break;
}
ll a = (1 << msb), b = 0;
for (i = msb - 1; i >= 0; i--)
if ((1 << i)&n)
{
b += (1 << i);
}
else
{
a += (1 << i);
b += (1 << i);
}
cout << a*b;
}
return 0;
}
```

**Alternate Approach**

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
while (t--)
{
ll i, j, k, n, m;
cin >> n;
ll ans = 0;
for (i = 0; i < n + 1; i++)
ans = max(ans, i * (n ^ i));
cout << ans;
}
return 0;
}
```