Links

2939. 最大异或乘积

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

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

题目描述

给你三个整数 abn ,请你返回 (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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。