Search code examples
bit-manipulationxor

Code to find X such that the product (A ^ X) * (B ^ X) is maximised

Find X such that (A ^ X) * (B ^ X) is maximum

Given A, B, and N (X < 2^N)

Return the maximum product modulus 10^9+7.

Example:

A = 4
B = 6
N = 3
We can choose X = 3 and (A ^ X) = 7 and (B ^ X) = 5.
The product will be 35 which is the maximum.

Here is my code:

int limit = (1<<n) - 1;
int MOD = 1_000_000_007;
int maxProd = 1;
for(int i = 1; i <= limit; i++){
  int x1 = (A^i);
  int x2 = (B^i);
  maxProd = max(maxProd, (x1*x2) % MOD);
}
return maxProd;
Solution
    1. for bits >=Nth bit, X will be zero, A^X and B^X are A and B for those bits
    2. find set bits and zero bits shared by A and B from 0 to N-1th bits. for set bits, X will be zero there. for zero bits, X will be 1 there.
    3. for bits that A and B are different, X will be either 0 or 1

    from 1,2, we will have the value for A and B, denoted by a and b. a and b are known constants

    from 3, we will have a bunch of 2^k, such as 2^3, 2^1,…, say the tot sum of them is tot. tot is a known constant

    the question becomes max (a+tot-sth)*(b+sth), where sth is the subset sum of some 2^k from 3, while a,tot,and b are constants

    when (a+tot-sth) and (b+sth) are as close as possible, the product will be maxed.

    if a==b, we will give the most significant bit of step 3 to either a or b, and the rest to the other one if a!=b, we will give all bits in step 3 to the smaller one