#2939

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Xor Product

Find the maximum value of (a XOR x) * (b XOR x) using greedy bitwise choices and invariant validation.

Problem Statement

Given three integers a, b, and n, compute the maximum value of (a XOR x) * (b XOR x) where x ranges from 0 to 2^n - 1. Return the result modulo 10^9 + 7. XOR refers to the bitwise exclusive OR operation.

You must select x carefully to maximize the product using a greedy approach on each bit while validating that choices maintain feasibility. Constraints are 0 <= a, b < 250 and 0 <= n <= 50.

Examples

Example 1

Input: a = 12, b = 5, n = 4

Output: 98

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

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

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 < 250
0 <= n <= 50

Solution Approach

Greedy Bit Selection

Iterate over bits from the most significant to least significant. At each bit, choose 1 or 0 for x to maximize the partial product. This leverages the greedy choice principle and avoids brute-force evaluation.

Invariant Validation

After each bit decision, verify that the remaining possible x values do not exceed 2^n. This ensures that every choice maintains feasibility and prevents overflows, aligning with the problem's pattern of invariant validation.

Modulo Handling

Since the product can be large, apply modulo 10^9 + 7 at each calculation. This keeps intermediate results manageable and avoids integer overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on n, iterating over each of the n bits once for greedy selection. Space complexity is minimal, using a few variables for current x and partial products.

What Interviewers Usually Probe

Look for an approach that avoids checking all 2^n x values.
Consider greedy decisions from the most significant bit to the least significant.
Ensure choices respect the upper bound 2^n and maintain feasibility at each step.

Common Pitfalls or Variants

Common pitfalls

Attempting brute-force over all x, leading to exponential runtime.
Failing to validate that bit choices keep x below 2^n, which can produce invalid results.
Neglecting modulo operation and causing integer overflow in intermediate products.

Follow-up variants

Change the upper bound 2^n to a larger limit and adjust bit selection accordingly.
Maximize sum instead of product using a similar greedy XOR approach.
Consider three numbers a, b, c and maximize (a XOR x)(b XOR x)(c XOR x).

FAQ

What is the key pattern in Maximum Xor Product?

The key pattern is greedy choice plus invariant validation, selecting bits from most to least significant to maximize (a XOR x)*(b XOR x).

Why is modulo 10^9 + 7 needed?

Products can exceed standard integer limits, so modulo ensures results stay within allowed numeric range.

Can brute-force work for this problem?

Brute-force is infeasible for larger n since it requires checking 2^n possibilities. Greedy bitwise selection is efficient.

How do I choose bits for x optimally?

Start from the most significant bit and choose the value that maximizes the current XOR product while keeping x < 2^n.

Are there variations of Maximum Xor Product?

Yes, you can vary the number of operands, the operation (sum or product), or the upper bound for x while using similar greedy techniques.

terminal

Solution

Solution 1: Greedy + Bitwise Operation

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        mod = 10**9 + 7
        ax, bx = (a >> n) << n, (b >> n) << n
        for i in range(n - 1, -1, -1):
            x = a >> i & 1
            y = b >> i & 1
            if x == y:
                ax |= 1 << i
                bx |= 1 << i
            elif ax > bx:
                bx |= 1 << i
            else:
                ax |= 1 << i
        return ax * bx % mod

Continue Practicing

#2967 minimum cost to make array equalindromic #2897 apply operations on array to maximize sum of squares #2871 split array into maximum number of subarrays