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.

#2939

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最大异或乘积

给你三个整数 a ， b 和 n ，请你返回 (a XOR x) * (b XOR x) 的最大值且 x 需要满足 0 n 。由于答案可能会很大，返回它对 10 9 + 7 取余后的结果。注意， XOR 是按位异或操作。示例 1：输入： a = 12, b = 5, n = 4 输出…

数学贪心位运算

题目描述

给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2ⁿ。

由于答案可能会很大，返回它对 10⁹+ 7 取余后的结果。

注意，XOR 是按位异或操作。

示例 1：

输入：a = 12, b = 5, n = 4
输出：98
解释：当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。
98 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

示例 2：

输入：a = 6, b = 7 , n = 5
输出：930
解释：当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。
930 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

示例 3：

输入：a = 1, b = 6, n = 3
输出：12
解释： 当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。
12 是所有满足 0 <= x < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

提示：

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

lightbulb

解题思路

方法一：贪心 + 位运算

根据题目描述，我们可以给 $a$ 和 $b$ 在二进制下 $[0..n)$ 位上同时分配一个数字，最终使得 $a$ 和 $b$ 的乘积最大。

因此，我们首先提取 $a$ 和 $b$ 高于 $n$ 位的部分，分别记为 $ax$ 和 $bx$ 。

接下来，从大到小考虑 $[0..n)$ 位上的每一位，我们将 $a$ 和 $b$ 的当前位分别记为 $x$ 和 $y$ 。

如果 $x = y$ ，那么我们可以将 $ax$ 和 $bx$ 的当前位同时置为 $1$ ，因此，我们更新 $ax = ax \mid 1 << i$ 和 $bx = bx \mid 1 << i$ 。否则，如果 $ax \lt bx$ ，要使得最终的乘积最大，我们应该让 $ax$ 的当前位置为 $1$ ，否则我们可以将 $bx$ 的当前位置为 $1$ 。

最后，我们返回 $ax \times bx \bmod (10^9 + 7)$ 即为答案。

时间复杂度 $O(n)$ ，其中 $n$ 为题目给定的整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2967 使数组成为等数数组的最小代价 #2897 对数组执行操作使平方和最大 #2871 将数组分割成最多数目的子数组