Maximize a Product Under a Shared Bounded XOR Choice
Company: Zomato
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Maximize a Product Under a Shared Bounded XOR Choice
You are given integers `a`, `b`, and `n`. Choose an integer `x` satisfying `0 <= x < 2^n` to maximize `(a XOR x) * (b XOR x)`, where `XOR` is the bitwise exclusive-or operation.
Return the maximum product modulo `10^9 + 7`. Maximize the actual product before taking its remainder.
### Examples
**Example 1**
```text
Input: a = 4, b = 7, n = 3
Output: 30
```
Choosing `x = 1` gives `(4 XOR 1) * (7 XOR 1) = 5 * 6 = 30`. For `x = 0,1,2,3,4,5,6,7`, the products are respectively `28,30,30,28,0,2,2,0`, so the maximum is `30`.
**Example 2**
```text
Input: a = 5, b = 9, n = 0
Output: 45
```
Since `2^0 = 1`, the only allowed choice is `x = 0`. The product is `5 * 9 = 45`.
### Constraints
- `0 <= a, b < 2^50`.
- `0 <= n <= 50`.
### Clarifying Questions
- Is the same `x` used in both factors? Yes.
- Can bits of `x` at positions `n` or higher be set? No; the strict bound `x < 2^n` forbids them.
- What happens when `n = 0`? Only `x = 0` is allowed.
- Must `a`, `b`, or the final factors be positive? No; zero is permitted.
- Do we return `x`? No; return the maximum product modulo the specified modulus. Different optimal `x` values may exist.
### C++ Interface
```cpp
class Solution {
public:
int maximumXorProduct(long long a, long long b, int n) {
}
};
```
### Reasoning Checkpoints
- Preserve the higher bits that the allowed `x` cannot change.
- Explain how a shared XOR choice couples the two factors.
- Justify the global maximum and avoid storing an overflowing unreduced product.
```hint Construct the factors from higher bits downward
At an adjustable bit where a and b agree, both output bits can be made one. Where they differ, exactly one output bit is one. With a fixed factor sum, a smaller difference between the factors gives a larger product.
```
Overview: Choose one integer below two to the nth power to XOR with both inputs, maximizing their product before returning its required modular remainder.