# Maximum Xor Product
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-xor-product)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-product
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
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
## 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.
**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).
**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.
### Explanation
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`.

```java
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();
    }
}
```
### 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`.

## Greedy Bitwise Construction
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int maximumXorProduct(long a, long b, int n) {
        long resA = 0;
        long resB = 0;
        long MOD = 1_000_000_007;

        for (int i = 49; i >= 0; i--) {
            long mask = 1L << i;
            long bit_a = a & mask;
            long bit_b = b & mask;

            if (i < n) { // We can choose x_i
                if (bit_a == bit_b) {
                    // If bits of a and b are same, we can make both resulting bits 1.
                    // This is always optimal. e.g., if a_i=b_i=0, choose x_i=1 -> resA_i=1, resB_i=1.
                    // if a_i=b_i=1, choose x_i=0 -> resA_i=1, resB_i=1.
                    resA |= mask;
                    resB |= mask;
                } else {
                    // Bits are different, one result must be 1, other 0.
                    // To maximize product, give the '1' to the smaller number to balance them.
                    if (resA < resB) {
                        resA |= mask; // Make resA larger
                    } else {
                        resB |= mask; // Make resB larger (or if they are equal)
                    }
                }
            } else { // x_i must be 0, so result bits are same as a_i and b_i
                if (bit_a != 0) {
                    resA |= mask;
                }
                if (bit_b != 0) {
                    resB |= mask;
                }
            }
        }

        resA %= MOD;
        resB %= MOD;

        return (int) ((resA * resB) % MOD);
    }
}
```
### 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    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

```