Medium

题目描述

给定三个整数 a、b 和 n，返回 (a XOR x) * (b XOR x) 的最大值，其中 0 <= x < 2^n。

由于答案可能很大，请返回对 10^9 + 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。
可以证明，对于所有 0 <= x < 2^n，98 是 (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。
可以证明，对于所有 0 <= x < 2^n，930 是 (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。
可以证明，对于所有 0 <= x < 2^n，12 是 (a XOR x) * (b XOR x) 的最大值。

约束条件：

  • 0 <= a, b < 2^50
  • 0 <= n <= 50

解题思路

这是一道贪心 + 位操作的经典题目。核心思想是从高位到低位逐位确定 x 的值，使得 (a XOR x) * (b XOR x) 最大化。

关键观察：

  1. 我们需要逐位分析，从最高位（第 n-1 位）开始到第 0 位
  2. 对于第 i 位，如果 a 和 b 在该位的值相同，我们可以让 x 在该位取不同值，使得 a XOR x 和 b XOR x 在该位都为 1
  3. 如果 a 和 b 在该位的值不同，只能让其中一个在该位为 1。此时应该让当前较小的数在该位变为 1，以平衡两个数的大小

算法流程：

  1. 对于每一位 i（从 n-1 到 0）：

    • 如果 a 和 b 在该位相同，设置 x 在该位为 1（使两个结果都在该位为 1）
    • 如果 a 和 b 在该位不同，比较当前的 a XOR x 和 b XOR x 的大小，让较小的那个在该位设为 1

  2. 这样构造出的 x 能使乘积最大化，因为我们总是优先让高位尽可能大，并且平衡两个数的大小

推荐解法： 贪心位操作算法，时间复杂度 O(n)，是最优解法。

代码实现

class Solution {
public:
    int maximumXorProduct(long long a, long long b, int n) {
        const int MOD = 1e9 + 7;
        
        // 从高位到低位处理
        for (int i = n - 1; i >= 0; i--) {
            long long bit = 1LL << i;
            long long bitA = a & bit;
            long long bitB = b & bit;
            
            if (bitA == bitB) {
                // a和b在第i位相同，可以让两个结果都在该位为1
                a |= bit;
                b |= bit;
            } else {
                // a和b在第i位不同，让较小的数在该位为1
                if (a < b) {
                    a |= bit;
                    b &= ~bit;
                } else {
                    a &= ~bit;
                    b |= bit;
                }
            }
        }
        
        return (a % MOD) * (b % MOD) % MOD;
    }
};

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10**9 + 7
        
        # 从高位到低位处理
        for i in range(n - 1, -1, -1):
            bit = 1 << i
            bit_a = a & bit
            bit_b = b & bit
            
            if bit_a == bit_b:
                # a和b在第i位相同，可以让两个结果都在该位为1
                a |= bit
                b |= bit
            else:
                # a和b在第i位不同，让较小的数在该位为1
                if a < b:
                    a |= bit
                    b &= ~bit
                else:
                    a &= ~bit
                    b |= bit
        
        return (a % MOD) * (b % MOD) % MOD

public class Solution {
    public int MaximumXorProduct(long a, long b, int n) {
        const int MOD = 1000000007;
        
        // 从高位到低位处理
        for (int i = n - 1; i >= 0; i--) {
            long bit = 1L << i;
            long bitA = a & bit;
            long bitB = b & bit;
            
            if (bitA == bitB) {
                // a和b在第i位相同，可以让两个结果都在该位为1
                a |= bit;
                b |= bit;
            } else {
                // a和b在第i位不同，让较小的数在该位为1
                if (a < b) {
                    a |= bit;
                    b &= ~bit;
                } else {
                    a &= ~bit;
                    b |= bit;
                }
            }
        }
        
        return (int)((a % MOD) * (b % MOD) % MOD);
    }
}

var maximumXorProduct = function(a, b, n) {
    const MOD = 1000000007;
    
    let x = 0n;
    
    for (let i = n - 1; i >= 0; i--) {
        const bitA = (BigInt(a) >> BigInt(i)) & 1n;
        const bitB = (BigInt(b) >> BigInt(i)) & 1n;
        
        const option0 = (BigInt(a) ^ x) * (BigInt(b) ^ x);
        const option1 = (BigInt(a) ^ (x | (1n << BigInt(i)))) * (BigInt(b) ^ (x | (1n << BigInt(i))));
        
        if (option1 > option0) {
            x |= (1n << BigInt(i));
        }
    }
    
    const result = (BigInt(a) ^ x) * (BigInt(b) ^ x);
    return Number(result % BigInt(MOD));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目