↓Skip to main content
  1. Posts/

LeetCode-2939 最大异或乘积

·1 min·
Table of Contents

LeetCode-2939 最大异或乘积 #

Solution 1 #

通过改变 $x$ , 可以对 $a, b$ 的前 $n$ 位进行操作. 考虑第 $i$ 位:

  • $a, b$ 均为 $1$: 不变.
  • $a, b$ 均为 $0$: 均变为 $1$.
  • $a, b$ 一个为 $0$, 一个为 $1$: 可以选择是否将这一位调换, 这个操作对总和没有影响.

因此, 问题是总和固定的情况, 在一定限制内增减 $a, b$ 让乘积最大. 我们要做的事情实际上是将前两种操作执行完后, 调换同一位上的 $0$ 和 $1$ 让 $a,b$ 更接近.

代码如下:

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10 ** 9 + 7
        book = []
        for i in range(n):
            a_i = a & (1 << i)
            b_i = b & (1 << i)
            if a_i == 0 and b_i == 0:
                a |= 1 << i
                b |= 1 << i
            elif a_i != 0 and b_i != 0:
                continue
            else:
                a &= ~(1 << i)
                b &= ~(1 << i)
                book.append(1 << i)
        for v in book[::-1]:
            a, b = min(a, b) + v, max(a, b)
        return a * b % MOD