Skip to content

Latest commit

 

History

History
130 lines (79 loc) · 4.89 KB

2939.maximum-xor-product.md

File metadata and controls

130 lines (79 loc) · 4.89 KB
Raw

题目地址(2939. 最大异或乘积 - 力扣（LeetCode）)

https://leetcode.cn/problems/maximum-xor-product/

题目描述

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

由于答案可能会很大，返回它对 109 + 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 < 2n 中 (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 < 2n 中 (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 < 2n 中 (a XOR x) * (b XOR x) 的最大值。

 

提示：

  • 0 <= a, b < 250
  • 0 <= n <= 50

前置知识

  • 位运算

公司

  • 暂无

思路

题目是求 a xor x 和 b xor x 的乘积最大。x 的取值范围是 0 <= x < 2^n。为了方便这里我们 a xor x 记做 axorx，b xor x 记做 bxorx，

首先我们要注意。对于除了低 n 位，其他位不受 x 异或影响。因为 x 除了低 n 可能不是 1，其他位都是 0。而 0 与任何数异或还是自身，不会改变。

因此我们能改的只是低 n 位。那么 x 的低 n 位具体去多少才可以呢？

朴素地枚举每一位上是 0 还是 1 的时间复杂度是 $2^n$，无法通过。

我们不妨逐位考虑。对于每一位：

  • 如果 a 和 b 在当前位相同， 那么 x 只要和其取相反的就行，异或答案就是 1。
  • 如果 a 和 b 在当前位不同， 那么 axorx 在当前位的值与bxorx 在当前位的值吧必然一个是 0 一个是 1，那么让哪个是 1，哪个是 0 才能使得乘积最大么？

根据初中的知识，对于和相同的两个数，两者数相差的越小乘积越大。因此我们的策略就是 axorx 和 bxorx 哪个小就让他大一点，这样可以使得两者差更小。

那么没有最终计算出来 axorx 和 bxorx，怎么提前知道哪个大哪个小呢？其实我们可以从高位往低位遍历，这样不用具体算出来 axorx 和 bxorx 也能知道大小关系啦。

关键点

  • 除了低 n 位，其他不受 x 异或影响
  • 对于每一位，贪心地使得异或结果为 1， 如果不能，贪心地使较小的异或结果为 1

Code

  • 语言支持：Python3

Python3 Code:

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        axorx = (a >> n) << n # 低 n 位去掉，剩下的前 m 位就是答案中的 axorb 二进制位。剩下要做的是确定低 n 位具体是多少
        bxorx = (b >> n) << n
        MOD = 10 ** 9 + 7
        for i in range(n-1, -1, -1):
            t1 = a >> i & 1
            t2 = b >> i & 1
            if t1 == t2:
                axorx |= 1 << i
                bxorx |= 1 << i
            else:
                if axorx < bxorx:
                    axorx |= 1 << i # 和一定，两者相差越小，乘积越大 
                else:
                    bxorx |= 1 << i
        axorx %= MOD
        bxorx %= MOD
        return (axorx * bxorx) % MOD

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。