LC 1486. 数组异或操作

题目描述

这是 LeetCode 上的 1486. 数组异或操作 ，难度为 简单。

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

示例 1：

1
2
3
4
5
6
输入：n = 5, start = 0

输出：8

解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

示例 2：
1
2
3
4
5
输入：n = 4, start = 3

输出：8

解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：
1
2
3
输入：n = 1, start = 7

输出：7

示例 4：
1
2
3
输入：n = 10, start = 5

输出：2

提示：

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

模拟

数据范围只有 $10^3$，按照题目要求从头模拟一遍即可。

代码：

1
2
3
4
5
6
7
8
9
10
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(1)$

数学

上述解法数据范围出到 $10^8$ 大概率会发生 TLE。

如果数据范围出到 $10^8$ 的话，本题难度应该会归为「中等」或「困难」。

事实上，本题存在「数学规律」解法。

原式子为 $start ⊕ (start + 2) ⊕ (start + 4) ⊕ … ⊕ (start + 2 * (n - 1))$ 。

我们发现原式子中只有数值 $2$ 是固定系数（由题目给定），考虑将其进行提出。

得到新式子 $s ⊕ (s + 1) ⊕ (s + 2) ⊕ … ⊕ (s + (n - 1)) * 2$，其中 $s = start / 2$。

之所以进行这样的转换操作，是因为我们想要利用 $1 ⊕ 2 ⊕ 3 = 0$ 的异或性质。

但是转换到了这一步，我们发现「新式子」与「原式子」其实并不相等。

我们需要考虑两者之间的差值关系：

不难发现，将「原式」转化成「新式」的集体除以 $2$ 的操作相当于将每个 $item$ 的进行「右移一位」，同时「异或运算」是每位独立计算的，因此「右移一位」不会影响移动部分的计算结果。

本质上，「原式」转化成「新式」是将最终答案 ans 进了「右移」一位的操作。因此如果要重新得到 ans，我们需要将其重新「左移」一位，将最后一位异或结果补回。

即 原式结果 = 新式结果 << 1 | e，$e$ 为最后一位异或结果（只能是 $0$ 或者 $1$，其余高位为 $0$）。

我们重新观察「原式」发现式子中每个 $item$ 奇偶性相同，这意味着其二进制的最低位相同。

根据 n 和 start 的奇偶数搭配，不难得最后一位 e = n & start & 1。

剩下的问题在于如何在不遍历的情况下计算「新式」结果，前面说到转化的目的是为了利用 $1 ⊕ 2 ⊕ 3 = 0$ 异或特性。

事实上，这个式子存在一般性的推广结论：$4i ⊕ (4i + 1) ⊕ (4i + 2) ⊕ (4i + 3) = 0$。

因此只需要对最后一项进行 %4 讨论即可，这部分属于「结论」，详见代码的 calc 部分。

总结一下，假设我们最终的答案为 ans。整个处理过程其实就是把原式中的每个 $item$ 右移一位（除以 $2$），计算 ans 中除了最低一位以外的结果；然后再将 ans 进行一位左移（重新乘以 $2$），将原本丢失的最后一位结果重新补上。补上则是利用了 n 和 start 的「奇偶性」的讨论。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1486 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。