Maximum Xor Product

MEDIUM

Description

Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2ⁿ.

Since the answer may be too large, return it modulo 10⁹+ 7.

Note that XOR is the bitwise XOR operation.

Example 1:

Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98. 
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2ⁿ.

Example 2:

Input: a = 6, b = 7 , n = 5
Output: 930
Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930.
It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2ⁿ.

Example 3:

Input: a = 1, b = 6, n = 3
Output: 12
Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12.
It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2ⁿ.

Constraints:

0 <= a, b < 2⁵⁰
0 <= n <= 50

Approaches

Checkout 2 different approaches to solve Maximum Xor Product. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

The brute-force approach is the most straightforward way to solve the problem. It involves checking every single possible value for x within its allowed range, 0 <= x < 2^n. For each x, we compute the expression (a XOR x) * (b XOR x) and keep track of the maximum value found. While simple to conceptualize, this method is computationally expensive and not feasible for the problem's constraints.

Algorithm

Initialize a variable max_product to BigInteger.ZERO.
Determine the upper bound for x, which is 2^n. Let's call it limit.
Loop x from 0 to limit - 1.
- For each x, calculate val_a = a XOR x and val_b = b XOR x.
- Compute the product current_product = val_a * val_b.
- Compare current_product with max_product and update max_product if the current product is larger.
After the loop finishes, max_product will hold the maximum possible product.
Return max_product modulo 10^9 + 7.

This method iterates through all possible values of x from 0 to 2^n - 1. In each iteration, it calculates the two XORed values, a XOR x and b XOR x, and their product. It maintains a variable, max_product, initialized to zero, and updates it whenever a larger product is found.

Since a, b, and x can be large, their XOR results can also be large. The product (a XOR x) * (b XOR x) can exceed the capacity of a standard 64-bit integer (long in Java). For instance, if a, b, and x are around 2^50, the product can be around 2^100. Therefore, it's necessary to use a class that can handle arbitrarily large integers, such as java.math.BigInteger.

import java.math.BigInteger;

class Solution {
    public int maximumXorProduct(long a, long b, int n) {
        BigInteger maxProduct = BigInteger.ZERO;
        long limit = 1L << n;
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger mod = new BigInteger("1000000007");

        for (long x = 0; x < limit; x++) {
            BigInteger bigX = BigInteger.valueOf(x);
            BigInteger valA = bigA.xor(bigX);
            BigInteger valB = bigB.xor(bigX);
            BigInteger currentProduct = valA.multiply(valB);
            if (currentProduct.compareTo(maxProduct) > 0) {
                maxProduct = currentProduct;
            }
        }

        return maxProduct.mod(mod).intValue();
    }
}

Complexity Analysis

Time Complexity: O(2^n). The loop runs `2^n` times. With `n` up to 50, `2^50` is approximately `10^15`, which is computationally infeasible.Space Complexity: O(1) (excluding the storage for `BigInteger` which depends on the magnitude of the numbers, but is constant for the given constraints).

Pros and Cons

Pros:

Simple to understand and implement.
Guaranteed to find the correct maximum value if implemented correctly.

Cons:

Extremely inefficient, with a time complexity that is exponential in n.
Will result in a 'Time Limit Exceeded' error for the given constraints (n up to 50).
Requires using BigInteger to handle potentially very large products, which adds complexity and overhead.

Code Solutions

Checking out 3 solutions in different languages for Maximum Xor Product. Click on different languages to view the code.

class Solution {
public
  int maximumXorProduct(long a, long b, int n) {
    final int mod = (int)1 e9 + 7;
    long ax = (a >> n) << n;
    long bx = (b >> n) << n;
    for (int i = n - 1; i >= 0; --i) {
      long x = a >> i & 1;
      long y = b >> i & 1;
      if (x == y) {
        ax |= 1L << i;
        bx |= 1L << i;
      } else if (ax < bx) {
        ax |= 1L << i;
      } else {
        bx |= 1L << i;
      }
    }
    ax %= mod;
    bx %= mod;
    return (int)(ax * bx % mod);
  }
}

Video Solution

Watch the video walkthrough for Maximum Xor Product

Patterns:

MathGreedyBit Manipulation