Maximum Xor Product - Video Solutions
Maximum Xor Product | Super Detailed | Leetcode Weekly Contest 372 | Leetcode-2939
Maximum Xor Product - Video Solution
Watch 7 video solutions for Maximum Xor Product, a medium level problem involving Math, Greedy, Bit Manipulation. This walkthrough by codestorywithMIK has 11,953 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2n.
Since the answer may be too large, return it modulo 109 + 7.
Note that XOR is the bitwise XOR operation.
Example 1:
Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98.
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Example 2:
Input: a = 6, b = 7 , n = 5 Output: 930 Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930. It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Example 3:
Input: a = 1, b = 6, n = 3 Output: 12 Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12. It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Constraints:
0 <= a, b < 2500 <= n <= 50
Approach Overview
Problem Overview: You are given integers a, b, and n. Choose a number x such that 0 ≤ x < 2^n and maximize the product (a XOR x) * (b XOR x). Only the lowest n bits of x can change the result, so the task reduces to carefully choosing which of those bits to flip.
Approach 1: Brute Force Enumeration (O(2^n) time, O(1) space)
Try every possible value of x from 0 to 2^n - 1. For each candidate, compute a ^ x and b ^ x, multiply them, and track the maximum product. This approach directly follows the problem definition and uses basic bit manipulation operations. The downside is exponential growth: if n is large, iterating over all 2^n possibilities becomes infeasible. It works only when n is very small or when building intuition during early experimentation.
Approach 2: Optimized Binary Greedy Construction (O(n) time, O(1) space)
The product (a ^ x) * (b ^ x) is maximized when the two resulting numbers are both large and as balanced as possible. Instead of testing every x, build the result bit by bit from the most significant of the n adjustable bits down to the least significant. This uses a greedy strategy based on how XOR affects each bit.
For each bit position i in the range [0, n-1], inspect the corresponding bits in a and b. If the bits are equal, setting the bit in x to flip both values to 1 increases both numbers simultaneously, which improves the product. If the bits differ, only one of the two results can gain a 1. In that case, assign the bit so the smaller current value receives the 1. This greedy balancing step keeps the two numbers closer together, which maximizes their multiplication result. The technique combines ideas from greedy algorithms and math properties of products.
Bits above position n-1 remain unchanged because x cannot affect them. As you iterate through the controllable bits, update the partially constructed values of a ^ x and b ^ x. The final numbers yield the maximum product without exploring the full search space.
Recommended for interviews: Interviewers expect the greedy bit manipulation approach. The brute force method demonstrates understanding of XOR behavior, but the optimized approach shows you recognize that maximizing a product favors large, balanced operands and that bit decisions can be made independently from most significant to least significant.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(1) | Useful for very small n or verifying correctness during testing |
| Greedy Bit Manipulation | O(n) | O(1) | Optimal solution for large n; builds the best result bit by bit |