leetcode-1486-数组异或操作

数组异或操作

题面

leetcode题目

给你两个整数，n 和 start 。
数组 nums 定义为：\(nums[i] = start + 2 \times i\)（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。

example

输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (\(0 \oplus 2 \oplus 4 \oplus 6 \oplus 8\)) = 8 。

题解

总体思路

傻逼结论题，依赖两个结论:
1. \(4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0\)
2. 当x为奇数时 \(x \oplus (x-1) = 1\)

详细思路

题目要求: \[start \oplus (start + 2) \oplus (start + 4) \cdots \oplus (start + (n-1)\times2)\] 所有上式的子项的奇偶性相同，可以单独考虑最后一位，那么上式可以考虑为
\[(s \oplus (s + 1) \oplus (s+2) \oplus (s+3) \cdots \oplus(s + n - 1)) \times 2 + e\] 其中 \(s = \lfloor \frac{start}{2} \rfloor\)， 向下取整是因为当前不考虑最后一位。 这里的转化是先不考虑所有子项的最后一位，整体右移一位计算出结果后左移一位，加上最后一位的结果。
首先考虑\(e\)的值，\(e\)显然又和n的值与\(start\)的奇偶性有关，不难推断出当\(start\)为奇数且\(n\)为奇数的时候才为1，否则都为0。
到此，我们可以通过\(s\)在以\(4i\)开始的长度为4的序列的位置和n % 4的值通过分类讨论得出结果，但不够简洁。
此时我们可以套用一个套路，对于计算从a到b的某种计算的序列和，可以尝试是否能转变为计算\(f(b) \times f(a-1)\), 其中\(\times\)为对应的计算方式, \(f(x)\)为对应计算从\(1\)到\(x\)的计算和。
定义\[f(x) = 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \cdots \oplus x\] 则根据开篇的结论可知\(f(x)\)只有四种情况: \[ \begin{equation} \left\{ \begin{array}{lr} x, & x \% 4 = 0 \\ x \oplus (x - 1) = 1, & x \% 4 = 1\\ x \oplus(x - 1) \oplus (x - 2) = x \oplus 1 = x + 1, & x \% 4 = 2\\ x \oplus (x -1) \oplus (x - 2) \oplus (x - 3) = 0 & x \% 4 = 3 \end{array} \right. \end{equation} \] 原计算式则可以表达为\[(f(s+n-1) \oplus f(s-1))\times2 + e\]

代码

#include <iostream>
using namespace std;
// submit
class Solution
{
public:
    int xorOperation(int n, int start)
    {
        int e = 0;
        if (start % 2 != 0 && n % 2 != 0)
        {
            e = 1;
        }
        int s = start / 2;
        return (f(s + n - 1) \oplus f(s - 1)) \times 2 + e;
    }
    int f(int x)
    {
        switch (x % 4)
        {
        case 0:
            return x;
        case 1:
            return 1;
        case 2:
            return x + 1;
        case 3:
            return 0;
        }

        return 0;
    }
};

// for test
int main()
{
    Solution s;
    cout << s.xorOperation(5, 0) << endl;
    cout << s.xorOperation(4, 3) << endl;
    cout << s.xorOperation(1, 7) << endl;
    cout << s.xorOperation(10, 5) << endl;
    return 0;
}