Maximum Xor Product — Solution in Python, Java & C++
Maximum Xor Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and greedy.
Maximum Xor Product is a medium coding problem on math, greedy and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Greedy, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given three integers a, b and n, find the maximum value of (a XOR x) * (b XOR x) over all integers x with 0 <= x < 2^n.
The product can be huge, so return the maximum product taken modulo 10^9 + 7 (maximise the true product first, then reduce it).
CodeKairo bound: the original allows a, b < 2^50 and n <= 50; here a, b < 2^30 and n <= 30 so every input fits a 32-bit integer.
Example 1
Input: a = 3, b = 9, n = 2
Output: 27
Explanation: `x = 0` gives 3 × 9 = 27; `x = 1` gives 2 × 8 = 16, `x = 2` gives 1 × 11 and `x = 3` gives 0 × 10.
Example 2
Input: a = 0, b = 0, n = 3
Output: 49
Explanation: `x = 7` turns both into 7.
Example 3
Input: a = 1000000000, b = 1000000000, n = 0
Output: 49
Explanation: Only `x = 0` is allowed; 10^18 modulo 10^9 + 7 is 49.
Constraints
0 <= a, b < 2^300 <= n <= 30
Hints for Maximum Xor Product
Hint 1
xcan only change the lowestnbits ofaandb; everything above stays fixed.Hint 2
Within those bits, if
aandbagree at a position,xcan make both bits 1 — always worth it. If they disagree, exactly one of them gets the 1 whateverxis.Hint 3
For disagreeing bits the sum
a' + b'is fixed, and a product with a fixed sum is largest when the two factors are as close as possible: from the top bit down, give each disagreeing bit to whichever number is currently smaller.
How to solve Maximum Xor Product
Bits above n are fixed. Below n, matching bits can both become 1, and each mismatched bit lands in exactly one number — so the sum is fixed and the product is maximised by keeping the two numbers as balanced as possible.
Approach
- Walk
ifromn - 1down to 0 withbit = 2^i. - If
aandbhave the same value atbit, set it in both. - Otherwise, if
a > b(comparing the current values), make sure the bit ends up inb; else make sure it ends up ina— toggling both when it is on the wrong side (that is what XOR withxdoes). - Return
(a mod M) × (b mod M) mod MwithM = 10^9 + 7, multiplying in 64 bits.
Why it works
Setting a matching bit raises both factors, so it can only help. For mismatched bits the total a' + b' is the same for every choice of x, and for a fixed sum the product grows as the factors get closer. Processing from the highest bit, the factor that is currently smaller stays smaller whatever lower bits do (a lower bit is worth less than a higher one), so handing it each mismatched bit is optimal; when the high parts tie, either choice gives the same product by symmetry.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Maximise the real product, then take the modulus — comparing products after
modpicks the wrongx. - Reduce
aandbmoduloMbefore multiplying, and multiply in 64 bits: two values near 2^30 overflow 32-bit arithmetic. - With
n = 0the only choice isx = 0.
Reference solution
Python
def maximumXorProduct(a: int, b: int, n: int) -> int:
for i in range(n - 1, -1, -1):
bit = 1 << i
if (a & bit) == (b & bit):
a |= bit
b |= bit
elif a > b:
if a & bit:
a ^= bit
b ^= bit
else:
if b & bit:
a ^= bit
b ^= bit
return (a * b) % 1000000007Java
public static int maximumXorProduct(int a, int b, int n) {
for (int i = n - 1; i >= 0; i--) {
int bit = 1 << i;
if ((a & bit) == (b & bit)) { a |= bit; b |= bit; }
else if (a > b) { if ((a & bit) != 0) { a ^= bit; b ^= bit; } }
else { if ((b & bit) != 0) { a ^= bit; b ^= bit; } }
}
long M = 1000000007L;
return (int) ((a % M) * (b % M) % M);
}C++
int maximumXorProduct(int a, int b, int n) {
for (int i = n - 1; i >= 0; i--) {
int bit = 1 << i;
if ((a & bit) == (b & bit)) { a |= bit; b |= bit; }
else if (a > b) { if (a & bit) { a ^= bit; b ^= bit; } }
else { if (b & bit) { a ^= bit; b ^= bit; } }
}
const long long M = 1000000007LL;
return (int) ((a % M) * (b % M) % M);
}JavaScript
var maximumXorProduct = function(a, b, n) {
for (var i = n - 1; i >= 0; i--) {
var bit = 1 << i;
if ((a & bit) === (b & bit)) { a |= bit; b |= bit; }
else if (a > b) { if (a & bit) { a ^= bit; b ^= bit; } }
else { if (b & bit) { a ^= bit; b ^= bit; } }
}
var M = 1000000007;
a %= M;
b %= M;
return ((a * (b >>> 16)) % M * 65536 + a * (b & 65535)) % M;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms · Bit Manipulation