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;
}