Maximum XOR Product
Asked at Atlassian, Rippling
Problem
Given two integers a and b, find the maximum value of (a XOR x) * (b XOR x) for some integer x in the range [0, 2^n - 1] where n is the number of bits needed to represent both a and b. The greedy approach: for each bit, if a and b differ, set x's bit to 1 (flips both, one gains a 1-bit). If they're the same, set x's bit to 0 (both already agree).
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Key insight: (a XOR x) * (b XOR x) is maximized when both factors are as large as possible. For each bit position, decide whether setting x's bit to 0 or 1 makes the product larger.
Case 1: a's bit and b's bit differ (one is 0, one is 1). Setting x's bit to 1 flips both: the 0 becomes 1 and the 1 becomes 0. The product is maximized because we maximize the XOR result for the variable that had the 0.
Case 2: a's bit and b's bit are the same (both 0 or both 1). Setting x's bit to 0 keeps both the same. Setting x's bit to 1 flips both, which doesn't change their product (both gain or lose equally). So 0 is fine.
Wait, that's not quite right. Let's think deeper. Let u = a XOR x, v = b XOR x. We want to maximize u * v. At each bit, if a_bit != b_bit, then one of u, v gets a 1 and the other gets 0. We want to maximize u + v (AM-GM: product is maximized when sum is maximized and values are balanced).
Greedy: for each bit from MSB to LSB:
- If a_bit == b_bit: set x_bit = 0. Both XOR results keep this bit as-is. If both are 1, great. If both are 0, nothing we can do.
- If a_bit != b_bit: set x_bit = 1. This flips the 0 to 1 and the 1 to 0, making both XOR results have 1 at this position. This is always better.
Actually: if a_bit != b_bit, setting x_bit = 1 gives both results a 1 at this position. Setting x_bit = 0 gives one a 1 and the other a 0. We want both to have 1, so set x_bit = 1.
Build x by iterating from the highest bit to the lowest. If a_bit XOR b_bit == 1 (they differ), set x_bit = 1. Otherwise, set x_bit = 0. Then compute (a XOR x) * (b XOR x).
Time: O(n) where n is the number of bits (at most 60 for 64-bit integers). Space: O(1).
Optimal Approach
Greedy bit construction:
- Find the maximum bit position needed:
max_bit = max(a, b).bit_length(). - Initialize x = 0.
- For i from max_bit - 1 down to 0:
a. If the i-th bit of a differs from the i-th bit of b (i.e.,(a >> i) & 1 != (b >> i) & 1), set the i-th bit of x:x |= (1 << i). - Return
(a XOR x) * (b XOR x).
Why this works: when a_bit != b_bit, setting x_bit = 1 gives both (a XOR x) and (b XOR x) a 1 at this position. When a_bit == b_bit, either choice is equivalent, so we leave x_bit = 0.
Walkthrough: a = 12 (1100), b = 5 (0101).
- Bit 3: a=1, b=0. Differ. Set x_bit=1. x = 1000.
- Bit 2: a=1, b=1. Same. x_bit=0.
- Bit 1: a=0, b=0. Same. x_bit=0.
- Bit 0: a=0, b=1. Differ. Set x_bit=1. x = 1001.
- a XOR x = 1100 XOR 1001 = 0101 = 5.
- b XOR x = 0101 XOR 1001 = 1100 = 12.
- Product = 5 * 12 = 60.
Time: O(log(max(a,b))). Space: O(1).
What Trips People Up in Real Interviews
Not recognizing the bit-level decision. Each bit of x is independent of the others. You can decide each bit greedily without considering interactions between bits.
Using brute force over all possible x values. If a and b are up to 10^9, x can be up to 2^30, which is too many to enumerate. The greedy bit approach is O(log(max(a,b))).
Confusing XOR with AND or OR. Remember: a XOR x flips bits of a where x has 1s. If a_bit = 0 and x_bit = 1, result_bit = 1. If a_bit = 1 and x_bit = 1, result_bit = 0.
Forgetting to compute the product at the end. After building x, you still need to compute (a XOR x) * (b XOR x) and return it. Don't return x itself.
Not handling the case where a and b are 0. If both are 0, any x gives 0 * 0 = 0. The algorithm handles this correctly since all bits are equal, so x = 0.
Solution Code
def maximumXORProduct(a, b, n=0):
if n == 0:
n = max(a.bit_length(), b.bit_length())
x = 0
for i in range(n - 1, -1, -1):
a_bit = (a >> i) & 1
b_bit = (b >> i) & 1
if a_bit != b_bit:
x |= (1 << i)
return (a ^ x) * (b ^ x)Frequently Asked Questions
What is the Maximum XOR Product problem?
Given two integers a and b, find the maximum value of (a XOR x) * (b XOR x) for some integer x in the range [0, 2^n - 1] where n is the number of bits needed to represent both a and b. The greedy approach: for each bit, if a and b differ, set x's bit to 1 (flips both, one gains a 1-bit). If they're the same, set x's bit to 0 (both already agree).
How do you solve Maximum XOR Product?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum XOR Product?
Maximum XOR Product is asked at Atlassian, Rippling. It is a medium difficulty problem.
What are common mistakes on Maximum XOR Product?
- Not recognizing the bit-level decision. Each bit of x is independent of the others. You can decide each bit greedily without considering interactions between bits.
- Using brute force over all possible x values. If a and b are up to 10^9, x can be up to 2^30, which is too many to enumerate. The greedy bit approach is `O(log(max(a,b)))`.
- Confusing XOR with AND or OR. Remember: `a XOR x` flips bits of a where x has 1s. If a_bit = 0 and x_bit = 1, result_bit = 1. If a_bit = 1 and x_bit = 1, result_bit = 0.
- Forgetting to compute the product at the end. After building x, you still need to compute (a XOR x) * (b XOR x) and return it. Don't return x itself.
- Not handling the case where a and b are 0. If both are 0, any x gives 0 * 0 = 0. The algorithm handles this correctly since all bits are equal, so x = 0.