LeetCode-2527 查询数组异或美丽值

LeetCode-2527 查询数组异或美丽值 #

Solution 1 #

由于不同二进制位上的位运算是独立的, 可以分开计算. 统计 $(x|y)&z = 1$ 的数量, 要求 $z=1$ 且 $x,y$ 不同时为 $0$ . 如果该位上有 $m$ 个 $1$, $n-m$ 个 $0$, 那么 $(x, y)$ 有 $n^2 - (n-m)^2$ 种, $z$ 有 $m$ 种, 总共有 $m(n^2 - (n-m)^2)\equiv m^3\equiv m\ \ \text{mod}\ 2$ 种, 结果等价于对这一位直接异或.

代码如下:

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        return reduce(xor, nums)