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 <= 50Problem 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.
The brute force approach involves iterating through all values of x from 0 to 2n - 1. For each x, compute (a XOR x) * (b XOR x) and keep track of the maximum value encountered. This approach is straightforward but not efficient for large values of n due to the exponential number of calculations involved.
This C program uses a simple for loop to iterate over all possible values of x from 0 to 2n-1. For each x, it computes the XOR product and checks if it's the maximum encountered so far. The result is obtained modulo 109 + 7.
Time Complexity: O(2n), Space Complexity: O(1)
To optimize, note that the highest bits have the greatest impact on the result. We can iterate only once, while considering the impact of x near (1 << n) - 1 or by choosing x that maximizes the resulting bits in XOR operations, effectively reducing unnecessary iterations.
This C code attempts to further optimize the solution by focusing on values of x derived from setting and unsetting specific bits. This method particularly focuses on dominating bit manipulations pausing only on those with the highest potential XOR.
Time Complexity: O(n), Space Complexity: O(1)
According to the problem description, we can assign a number to the [0..n) bits of a and b in binary at the same time, so that the product of a and b is maximized.
Therefore, we first extract the parts of a and b that are higher than the n bits, denoted as ax and bx.
Next, we consider each bit in [0..n) from high to low. We denote the current bits of a and b as x and y.
If x = y, then we can set the current bit of ax and bx to 1 at the same time. Therefore, we update ax = ax \mid 1 << i and bx = bx \mid 1 << i. Otherwise, if ax < bx, to maximize the final product, we should set the current bit of ax to 1. Otherwise, we can set the current bit of bx to 1.
Finally, we return ax times bx bmod (10^9 + 7) as the answer.
The time complexity is O(n), where n is the integer given in the problem. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(2n), Space Complexity: O(1) |
| Optimized Binary Manipulation Approach | Time Complexity: O(n), Space Complexity: O(1) |
| Greedy + Bitwise Operation | — |
| 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 |
Maximum Xor Product | Super Detailed | Leetcode Weekly Contest 372 | Leetcode-2939 • codestorywithMIK • 10,506 views views
Watch 9 more video solutions →Practice Maximum Xor Product with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor