2939. Maximum XOR Product
Asked at Atlassian, Rippling
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Math
Companies
2
Problem
You are given three integers a, b, and n. You must choose an integer x such that 0 <= x < 2^n.
For your chosen x, compute the two values a XOR x and b XOR x, then multiply them together. Return the largest possible product over all valid choices of x.
Because the product can be huge, return the answer modulo 10^9 + 7. Note that XOR is the bitwise exclusive-or operation: a bit in the result is 1 only when the two input bits differ.
Pick x to make both factors big
Constraints
- ●
0 <= a, b < 2^50 - ●
0 <= n <= 50
Examples
a = 12, b = 5, n = 498a = 6, b = 7, n = 5930a = 1, b = 6, n = 312Asked At
2 companies| 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).
Greedy bit by bit
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.