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

Math Greedy Bit Manipulation

Prompt

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 < 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 < 2⁵⁰
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.

1import java.math.BigInteger;2 3class Solution {4    public int maximumXorProduct(long a, long b, int n) {5        BigInteger maxProduct = BigInteger.ZERO;6        long limit = 1L << n;7        BigInteger bigA = BigInteger.valueOf(a);8        BigInteger bigB = BigInteger.valueOf(b);9        BigInteger mod = new BigInteger("1000000007");10 11        for (long x = 0; x < limit; x++) {12            BigInteger bigX = BigInteger.valueOf(x);13            BigInteger valA = bigA.xor(bigX);14            BigInteger valB = bigB.xor(bigX);15            BigInteger currentProduct = valA.multiply(valB);16            if (currentProduct.compareTo(maxProduct) > 0) {17                maxProduct = currentProduct;18            }19        }20 21        return maxProduct.mod(mod).intValue();22    }23}

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.

A highly efficient solution can be achieved using a greedy approach that constructs the optimal values of A = a XOR x and B = b XOR x bit by bit, from most significant to least significant. The core idea is that to maximize a product A * B, we should try to make both A and B as large as possible. When a conflict arises (i.e., we can only make one of them larger at a certain bit position), we make a choice that keeps their values as close as possible, which is a good heuristic for maximizing their product.

Algorithm

Initialize two long variables, resA and resB, to 0. These will be built into the final a XOR x and b XOR x values.
Iterate from the most significant bit, say 49, down to 0. Let the current bit be i.
For each bit i, get the i-th bits of a and b, let's call them bit_a and bit_b.
If i >= n: The i-th bit of x must be 0. The i-th bits of the results are determined solely by a and b. Set the i-th bit of resA to bit_a and resB to bit_b.
If i < n: We can choose the i-th bit of x.
- If bit_a is the same as bit_b: We can choose x_i to make the resulting bits (a XOR x)_i and (b XOR x)_i both 1. This is always optimal as it makes both numbers larger. So, we set the i-th bit in both resA and resB to 1.
- If bit_a is different from bit_b: The resulting bits must be different (one 1, one 0). To maximize the product, we want to keep resA and resB as close in value as possible. We compare the prefixes of resA and resB built so far (from bits higher than i).
  - If resA is currently smaller than resB, we give the 1-bit to resA to help it catch up.
  - Otherwise (if resA is greater or equal), we give the 1-bit to resB.
After the loop, resA and resB hold the optimal values.
Calculate (resA % MOD) * (resB % MOD) % MOD and return the result.

Walkthrough

We iterate through the bits from a high number (like 49, since a, b < 2^50) down to 0. We build up our target numbers, let's call them resA and resB, which will eventually be a XOR x and b XOR x.

For bits i at or above n, the corresponding bit of x must be 0. Thus, the bits of resA and resB are fixed and equal to the corresponding bits of a and b.

For bits i below n, we have a choice for x_i (0 or 1).

If the i-th bits of a and b are the same, we can choose x_i to make the i-th bit of both resA and resB equal to 1. This is always the best choice as it maximizes both numbers.
If the i-th bits of a and b are different, we can only set the i-th bit to 1 for one of the results, while the other gets a 0. To maximize the final product, we should try to make resA and resB as close to each other as possible. We look at the values of resA and resB constructed so far from the higher bits. If resA is currently smaller than resB, we assign the 1-bit to resA for the current position i. Otherwise, we assign it to resB.

This greedy strategy ensures that at each step, we make a locally optimal choice that leads to the global maximum.

1class Solution {2    public int maximumXorProduct(long a, long b, int n) {3        long resA = 0;4        long resB = 0;5        long MOD = 1_000_000_007;6 7        for (int i = 49; i >= 0; i--) {8            long mask = 1L << i;9            long bit_a = a & mask;10            long bit_b = b & mask;11 12            if (i < n) { // We can choose x_i13                if (bit_a == bit_b) {14                    // If bits of a and b are same, we can make both resulting bits 1.15                    // This is always optimal. e.g., if a_i=b_i=0, choose x_i=1 -> resA_i=1, resB_i=1.16                    // if a_i=b_i=1, choose x_i=0 -> resA_i=1, resB_i=1.17                    resA |= mask;18                    resB |= mask;19                } else {20                    // Bits are different, one result must be 1, other 0.21                    // To maximize product, give the '1' to the smaller number to balance them.22                    if (resA < resB) {23                        resA |= mask; // Make resA larger24                    } else {25                        resB |= mask; // Make resB larger (or if they are equal)26                    }27                }28            } else { // x_i must be 0, so result bits are same as a_i and b_i29                if (bit_a != 0) {30                    resA |= mask;31                }32                if (bit_b != 0) {33                    resB |= mask;34                }35            }36        }37 38        resA %= MOD;39        resB %= MOD;40 41        return (int) ((resA * resB) % MOD);42    }43}

Complexity

Time

O(k), where `k` is the number of bits in the numbers (e.g., 50). This is effectively constant time, O(1).

Space

O(1), as it only uses a few variables to store intermediate results.

Trade-offs

Pros

Extremely fast, with a constant time complexity.
Efficiently solves the problem for the given large constraints.
Requires only basic integer types (long) and bitwise operations.

Cons

The greedy logic is non-trivial and requires careful reasoning about bitwise operations and their effect on the product.

Solutions

Solution

1class Solution {2public3  int maximumXorProduct(long a, long b, int n) {4    final int mod = (int)1 e9 + 7;5    long ax = (a >> n) << n;6    long bx = (b >> n) << n;7    for (int i = n - 1; i >= 0; --i) {8      long x = a >> i & 1;9      long y = b >> i & 1;10      if (x == y) {11        ax |= 1L << i;12        bx |= 1L << i;13      } else if (ax < bx) {14        ax |= 1L << i;15      } else {16        bx |= 1L << i;17      }18    }19    ax %= mod;20    bx %= mod;21    return (int)(ax * bx % mod);22  }23}

1class Solution {2public:3  int maximumXorProduct(long long a, long long b, int n) {4    const int mod = 1e9 + 7;5    long long ax = (a >> n) << n, bx = (b >> n) << n;6    for (int i = n - 1; ~i; --i) {7      int x = a >> i & 1, y = b >> i & 1;8      if (x == y) {9        ax |= 1LL << i;10        bx |= 1LL << i;11      } else if (ax < bx) {12        ax |= 1LL << i;13      } else {14        bx |= 1LL << i;15      }16    }17    ax %= mod;18    bx %= mod;19    return ax * bx % mod;20  }21};

1class Solution:2    def maximumXorProduct(self, a: int, b: int, n: int) -> int: mod = 10 ** 9 + 7 ax, bx = (a >> n) << n, (b >> n) << n for i in range(n - 1, - 1, - 1): x = a >> i & 1 y = b >> i & 1 if x == y: ax |= 1 << i bx |= 1 << i elif ax > bx: bx |= 1 << i else: ax |= 1 << i return 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 problem