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

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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