Scale Engineer

Maximum Xor Product

Med
#2619Time: 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: O(1) (excluding the storage for `BigInteger` which depends on the magnitude of the numbers, but is constant for the given constraints).
Patterns
MathGreedyBit Manipulation

Prompt

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

Since the answer may be too large, return it modulo 109 + 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 < 2n.

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 < 2n.

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 < 2n.

 

Constraints:

  • 0 <= a, b < 250
  • 0 <= n <= 50

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1) (excluding the storage for `BigInteger` which depends on the magnitude of the numbers, but is constant for the given constraints).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem