Maximize a Product After a Shared XOR
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Maximize a Product After a Shared XOR
Given positive integers `a` and `b` and a bit width `n`, choose an integer `x` with `0 <= x < 2**n` that maximizes:
```text
(a XOR x) * (b XOR x)
```
Return the maximum product modulo `1_000_000_007`.
### Function Signature
```python
def maximum_xor_product(a: int, b: int, n: int) -> int:
...
```
### Constraints
- `1 <= n <= 30`
- `1 <= a < 2**n`
- `1 <= b < 2**n`
- `x` may use only the lowest `n` bits.
- Maximize the full integer product before applying the modulus.
### Examples
```text
Input: a = 1, b = 2, n = 2
Output: 2
Input: a = 1, b = 6, n = 3
Output: 12
```
For the second example, `x = 2` produces `(1 XOR 2) * (6 XOR 2) = 3 * 4 = 12`.
### Clarifications
- Return the maximum product value, not the maximizing `x`.
- If several values of `x` produce the same maximum, the returned result is unchanged.
Quick Answer: Choose an n-bit value x that maximizes the product of (a XOR x) and (b XOR x). Determine the true maximum before applying the required modulo, using bitwise reasoning to allocate shared and differing bits effectively.
Choose an n-bit integer x maximizing (a XOR x) times (b XOR x), then return that maximum product modulo 1,000,000,007. The full integer product is optimized before reduction.
Constraints
- 1 <= n <= 30.
- Both inputs are positive and smaller than 2**n.
- x uses only the lowest n bits.
- Return the product value, not x.
Examples
Input: {'a':1,'b':2,'n':2}
Expected Output: 2
Explanation: The first supplied example.
Input: {'a':1,'b':6,'n':3}
Expected Output: 12
Explanation: The second supplied example.
Hints
- At equal input bits, x can make both result bits one.
- At differing bits, exactly one result receives the bit; assigning high bits to the currently smaller prefix balances the factors.