# 1486. XOR Operation in an Array

## LeetCode [1486. XOR Operation in an Array](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Given an integer `n` and an integer `start`.

Define an array `nums` where `nums[i] = start + 2*i` (0-indexed) and `n == nums.length`.

Return the bitwise XOR of all elements of `nums`.

**Example 1:**

```
Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.
```

**Example 2:**

```
Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.
```

**Example 3:**

```
Input: n = 1, start = 7
Output: 7
```

**Example 4:**

```
Input: n = 10, start = 5
Output: 2
```

**Constraints:**

* `1 <= n <= 1000`
* `0 <= start <= 1000`
* `n == nums.length`

### Tags

Array, Bit Manipulation

### Solution

We can reduce the time complexity through mathematical operations.

Before we do that, let's review some characters of XOR:

1. $$x⊕x=0$$ ;
2. $$x⊕y=y⊕x$$;
3. $$(x⊕y)⊕z=x⊕(y⊕z)$$ ;
4. $$x⊕y⊕y=x$$ ;
5. $$∀i∈Z， 4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0$$;
6. $$N \oplus (N+1) \oplus ... \oplus M = \[1 \oplus 2 \oplus ... \oplus (N+1)] \oplus \[1 \oplus ... \oplus M-1 \oplus M]$$ .

To make use of the 5th property of XOR, we mutate the required function to:

$$start⊕(start+2i)⊕(start+4i)⊕⋯⊕(start+2(n−1)) \Leftrightarrow (s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))×2+e, s=⌊ start/2 ⌋, e = n\&start&1$$

In this formula, `e` is the lowest bit and it is equal to 1 if and only if `n` and `start` are both odd numbers.

To obtain $$temp = (s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))$$ , based on the property 6, we only need to compute $$\[1 \oplus 2 \oplus ... \oplus (s-1)] \oplus \[1 \oplus ... \oplus (s-n+1)]$$ . Note that the pattern of XOR of the first `n` numbers is `n, 1, n+1, 0`.

Finally, we return the recovered result `temp * 2 + e`.

### Complexity

* Time complexity: $$O(1)$$
* Space complexity: $$O(1)$$

### Code

```go
func xorOperation(n int, start int) int {
	// the lowest bit is 1 if and only if n and start are both odd numbers
	lowestBit := n & start & 1

	// start ^ (start+2) ^ (start+4) ^ ... ^(start + 2*(n-1))
	// let s = start / 2
	// <=> (s ^ (s+1) ^ (s+2) ^ ... ^ (s+n-1)) * 2 + lowestBit
	s := start >> 1

	// ^(N ... M) = ^(1 ... N-1) ^ ^(1 ... M)
	temp := computeXOR(s-1) ^ computeXOR(s+n-1)
	return temp<<1 | lowestBit
}

func computeXOR(x int) int {
	// The pattern of XOR of the first n numbers
	//      n   binary ^(0...N)   return
	//      1    0001    0001        1
	//      2    0010    0011       n+1
	//      3    0011    0000        0
	//      4    0100    0100        n
	//      5    0101    0001        1
	//      6    0110    0111       n+1
	//      ……   ……      ……
	switch x % 4 {
	case 0:
		return x
	case 1:
		return 1
	case 2:
		return x + 1
	default: // 3
		return 0
	}
}
```

## Reference

1. [小明做数学](https://leetcode-cn.com/problems/xor-operation-in-an-array/solution/xiao-ming-zuo-shu-xue-by-xiaohu9527-0pu7/)
2. [数组异或操作](https://leetcode-cn.com/problems/xor-operation-in-an-array/solution/shu-zu-yi-huo-cao-zuo-by-leetcode-solution/)