> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1486.-xor-operation-in-an-array.md).

# 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/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1486.-xor-operation-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.