What is the key concept for solving the Maximum XOR After Operations problem?

The key concept is understanding how to strategically apply XOR and AND operations to maximize the final XOR result of all array elements.

How do I optimize my solution for the Maximum XOR After Operations problem?

Optimizing requires efficient use of bitwise operations, reducing redundant computations, and applying operations only when necessary to achieve the maximum result.

What is the difficulty level of the Maximum XOR After Operations problem?

The problem is categorized as Medium difficulty due to the need to understand bitwise operations and optimize them over multiple iterations.

What are the main techniques used in the Maximum XOR After Operations problem?

The main techniques are bitwise manipulation using AND and XOR operations, followed by strategic evaluation to maximize the XOR result.

Can the Maximum XOR After Operations problem be solved without considering all possible x values?

No, considering all possible x values is essential, as different values influence the XOR outcome, and missing some can result in suboptimal solutions.

#2317

Medium

auto_awesome数组·数学

LeetCode 题解工作台

操作后的最大异或和

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择任意非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。注意， AND 是逐位与运算， XOR 是逐位异或运算。请你执行任意次更新操作，并返回 nums 中所…

数组数学位运算

题目描述

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择任意非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素最大逐位异或和。

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁸

lightbulb

解题思路

方法一：位运算

在一次操作中，我们可以把 $\textit{nums}[i]$ 更新为 $\textit{nums}[i] \text{ AND } (\textit{nums}[i] \text{ XOR } x)$ 。由于 $x$ 是任意非负整数，因此 $\textit{nums}[i] \oplus x$ 的结果是一个任意值，再与 $\textit{nums}[i]$ 逐位与运算，可以把 $\textit{nums}[i]$ 的二进制表示中的若干位 $1$ 变为 $0$ 。

而题目中要获取的是 $\textit{nums}$ 所有元素的最大逐位异或和，对于一个二进制位，只要在 $\textit{nums}$ 中存在一个元素对应的二进制位为 $1$ ，那么这个二进制位对于最大逐位异或和的贡献就是 $1$ 。因此答案就是 $\textit{nums}$ 中所有元素的逐位或运算的结果。

时间复杂度 $O(n)$ ，其中 $n$ 为 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of bitwise operations.
question_mark
Evaluates ability to optimize algorithms for bit manipulation.
question_mark
Assesses knowledge of iterative optimization techniques.

warning

常见陷阱

外企场景

error
Failing to consider all possible values for x, limiting potential XOR results.
error
Not optimizing the algorithm for large input sizes, leading to inefficiency.
error
Misunderstanding the impact of applying multiple XOR operations on a single element.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit the number of allowed operations and evaluate the effect on XOR.
arrow_right_alt
Introduce constraints on the values of x and explore its effect on the result.
arrow_right_alt
Test with large input arrays and optimize for both time and space complexity.

help

常见问题

外企场景

继续练习

#2527 查询数组异或美丽值 #2572 无平方子集计数 #1994 好子集的数目