Is Maximum Xor Product easy or hard?

Maximum Xor Product is typically rated Medium difficulty. The brute force idea is straightforward, but recognizing that the optimal solution can be built greedily using bit manipulation requires deeper insight into XOR behavior and how products are maximized.

How to solve Maximum Xor Product in O(n)?

Iterate through the n controllable bits from most significant to least significant. Examine the corresponding bits in a and b and decide whether to flip them using x. If the bits are equal, flip them so both become 1. If they differ, assign the bit so the smaller current value receives the 1. This greedy balancing maximizes the final product.

What is the best approach for Maximum Xor Product?

The best approach uses greedy bit manipulation. Instead of testing every possible x, construct the result bit by bit from the most significant adjustable bit. When the bits of a and b are equal, flip them to produce 1s in both numbers. When they differ, assign the bit so the smaller value gains the 1, keeping the product maximized. This runs in O(n) time and O(1) space.

What data structure is used in Maximum Xor Product?

No complex data structure is required. The solution relies on bitwise operations such as shifts, XOR, and bit masking. The main idea is analyzing individual bits and greedily constructing the optimal result.

What is the time complexity of Maximum Xor Product?

The optimal greedy solution runs in O(n) time where n is the number of bits you are allowed to modify. Each bit from 0 to n-1 is processed once. The space complexity is O(1) because only a few integer variables are maintained during the computation.

Maximum Xor Product Python or Java solution approach?

Both Python and Java implementations follow the same logic: iterate over the n bits, inspect bits from a and b, and greedily decide whether the bit in x should flip them. Maintain the running values of a XOR x and b XOR x while processing bits. The algorithm remains O(n) time and O(1) space regardless of language.

Is Maximum Xor Product asked at Google, Amazon, or Meta?

Bit manipulation and greedy optimization problems like Maximum Xor Product frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of XOR behavior, bitwise construction, and reasoning about how to maximize a mathematical expression efficiently.

Description Hints 3 Solution Video 58:42

2939. Maximum Xor Product

Medium30.3% acceptance4 companies

Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2ⁿ.

Since the answer may be too large, return it modulo 10⁹+ 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 < 2ⁿ.

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 < 2ⁿ.

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 < 2ⁿ.

Constraints:

0 <= a, b < 2⁵⁰
0 <= n <= 50

Asked at 4 companies

Squarepoint Capital Rippling Atlassian

Google

Topics

Hints open one at a time

Hint 1

Iterate over bits from most significant to least significant.

Hint 2

For the i^th bit, if both a and b have the same value, we can always make x’s i^th bit different from a and b, so a ^ x and b ^ x both have the i^th bit set.

Hint 3

Otherwise, we can only set the i^th bit of one of a ^ x or b ^ x. Depending on the previous bits of a ^ x or b ^ x, we should set the smaller value’s i^th bit.

58:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution