题目描述
这是 LeetCode 上的 1486. 数组异或操作 ，难度为 简单。
Tag : 「数学」、「模拟」
给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
示例 1：
输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。 复制代码
示例 2：
输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8. 复制代码
示例 3：
输入：n = 1, start = 7 输出：7 复制代码
示例 4：
输入：n = 10, start = 5 输出：2 复制代码
提示：
- 1 <= n <= 1000
- 0 <= start <= 1000
- n == nums.length
模拟
数据范围只有 10310^3103，按照题目要求从头模拟一遍即可。
代码：
class Solution { public int xorOperation(int n, int start) { int ans = start; for (int i = 1; i < n; i++) { int x = start + 2 * i; ans ^= x; } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
数学
上述解法数据范围出到 10810^8108 大概率会发生 TLE。
如果数据范围出到 10810^8108 的话，本题难度应该会归为「中等」或「困难」。
事实上，本题存在「数学规律」解法。
原式子为 start⊕(start+2)⊕(start+4)⊕...⊕(start+2∗(n−1))start ⊕ (start + 2) ⊕ (start + 4) ⊕ ... ⊕ (start + 2 * (n - 1))start⊕(start+2)⊕(start+4)⊕...⊕(start+2∗(n−1)) 。
我们发现原式子中只有数值 222 是固定系数（由题目给定），考虑将其进行提出。
得到新式子 s⊕(s+1)⊕(s+2)⊕...⊕(s+(n−1))∗2s ⊕ (s + 1) ⊕ (s + 2) ⊕ ... ⊕ (s + (n - 1)) * 2s⊕(s+1)⊕(s+2)⊕...⊕(s+(n−1))∗2，其中 s=start/2s = start / 2s=start/2。
之所以进行这样的转换操作，是因为我们想要利用 1⊕2⊕3=01 ⊕ 2 ⊕ 3 = 01⊕2⊕3=0 的异或性质。
但是转换到了这一步，我们发现「新式子」与「原式子」其实并不相等。
我们需要考虑两者之间的差值关系：
不难发现，将「原式」转化成「新式」的集体除以 222 的操作相当于将每个 itemitemitem 的进行「右移一位」，同时「异或运算」是每位独立计算的，因此「右移一位」不会影响移动部分的计算结果。
本质上，「原式」转化成「新式」是将最终答案 ans 进了「右移」一位的操作。因此如果要重新得到 ans，我们需要将其重新「左移」一位，将最后一位异或结果补回。
即 原式结果 = 新式结果 << 1 | e，eee 为最后一位异或结果（只能是 000 或者 111，其余高位为 000）。
我们重新观察「原式」发现式子中每个 itemitemitem 奇偶性相同，这意味着其二进制的最低位相同。
根据 n 和 start 的奇偶数搭配，不难得最后一位 e = n & start & 1。
剩下的问题在于如何在不遍历的情况下计算「新式」结果，前面说到转化的目的是为了利用 1⊕2⊕3=01 ⊕ 2 ⊕ 3 = 01⊕2⊕3=0 异或特性。
事实上，这个式子存在一般性的推广结论：4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=04i ⊕ (4i + 1) ⊕ (4i + 2) ⊕ (4i + 3) = 04i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0。
因此只需要对最后一项进行 %4 讨论即可，这部分属于「结论」，详见代码的 calc 部分。
总结一下，假设我们最终的答案为 ans。整个处理过程其实就是把原式中的每个 itemitemitem 右移一位（除以 222），计算 ans 中除了最低一位以外的结果；然后再将 ans 进行一位左移（重新乘以 222），将原本丢失的最后一位结果重新补上。补上则是利用了 n 和 start 的「奇偶性」的讨论。
代码：
class Solution { int calc(int x) { if (x % 4 == 0) return x; else if (x % 4 == 1) return 1; else if (x % 4 == 2) return x + 1; else return 0; } public int xorOperation(int n, int start) { // 整体除以 2，利用 %4 结论计算 ans 中除「最低一位」的结果 int s = start >> 1; int prefix = calc(s - 1) ^ calc(s + n - 1); // 利用「奇偶性」计算 ans 中的「最低一位」结果 int last = n & start & 1; int ans = prefix << 1 | last; return ans; } } 复制代码
- 时间复杂度：O(1)O(1)O(1)
- 空间复杂度：O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1486 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
